268. Missing Number

NSFish 发布于2019-08-14 14:18 / 1210人阅读

摘要：题目解答一开始我的思始很简单，排序，查找但是可以用的方法，因为只有一个，所以可以把其它所有的数都配好对，剩下这个就是我们要找的这里很喔，因为只少了一个数，举个例子所以当我们把这些数的时候，唯一一个剩下的就是的这个数

题目：
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

解答：
一开始我的思始很简单，排序，查找：

public int missingNumber(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int result = 0;
    
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        if (result != nums[i]) {
            return result;
        }
        result++;
    }
    return nums.length;
}

但是可以用xor的triky方法，因为只有一个missing number，所以可以把其它所有的数都配好对，剩下这个就是我们要找的number:

public int missingNumber(int[] nums) {
    int xor = 0, i = 0;
    
    //这里很triky喔，因为只少了一个数，举个例子：
    //nums: 1, 3, 4
    //   i: 1, 2, 3, (4)
    //所以当我们把这些数xor的时候，唯一一个剩下的就是2, missing的这个数
    
    for (i = 0; i < nums.length; i++) {
        xor = xor ^ i ^ nums[i];
    }
    
    return xor ^ i;
}

GPU云服务器云服务器 missing method_missing aapt is missing number

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64929.html

268. Missing Number

摘要：之后我们可以查看头尾两个数字是否符合要求。如果不符合我们可以直接返回结果。方法利用的特点。方法求和根据高斯定理，从到的和为。所以把数组的所有数字求和，然后与从到的和相减所得数字，就是我们需要的数字。题目链接：Missing Number 思路：方法1: 排序我们很自然的可以想到，如果数组是排好序的，那么可以很容易的找到缺少的数字。之后我们可以查看头尾两个数字是否符合要求。如果不符合我...

Steven 2019-07-30 17:01 评论0 收藏0
leetcode 268 Missing Number

摘要：题目详情题目的意思是输入一个长度为的数组，找到这个数字中不存在于数组中的丢失的数字思路我的想法是，用这个数的和减去数组中的每一个元素的值，最后剩下的值就是丢失的数字解法题目详情 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing fr...

tianyu 2019-08-15 13:54 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
LeetCode偶尔一题 —— 268. 缺失数字

摘要：题目描述给定一个包含中个数的序列，找出中没有出现在序列中的那个数。示例输入输出示例输入输出最简单的解法刚看到的这道题的时候，第一感觉就是排序，之后直接挨个比较就能找到缺失的数字。题目描述给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。示例 1: 输入: [3,0,1] 输出: 2 示例 2: 输入: [9,6,...

e10101 2019-08-26 10:22 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0