leetcode_268.missing number

ゝ一纸荒年。 2021-12-24 14:45 230阅读 0赞

给定一个数组nums，其中包含0--n中的n个数，找到数组中没有出现的那个数。

解法一：cyclic swapping algorithm

class Solution
    {
    public:
        int missingNumber(vector<int>& nums)
        {
            nums.push_back(-1);
            int len=nums.size();
            for(int i=0;i<len;i++)
            {
                while(nums[i]>=0 && nums[i]!=i)
                    swap(nums[i], nums[nums[i]]);
            }
            for(int i=0;i<=len;i++)
                if(nums[i]==-1)
                    return i;
            return -1;
        }
    };

解法二：用(1+n)\*n/2减掉数组中所有数，就是没有出现的那个数。

class Solution
    {
    public:
        int missingNumber(vector<int>& nums)
        {
            int n=nums.size(), sum = (1+n)*n/2;
            for(int i:nums)
                sum -= i;
            return sum;
        }
    };

解法三：使用异或运算符，a^b^b=a。

class Solution
    {
    public:
        int missingNumber(vector<int>& nums)
        {
            int result = nums.size();
            for(int i=0;i<nums.size();i++)
                result = result^i^nums[i];
            return result;
        }
    };

转载于:https://www.cnblogs.com/jasonlixuetao/p/10776701.html

发表评论取消回复

表情：

评论列表（有 0 条评论，230人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Easy - 268. Missing Number

Topic Array Math Bit Manipulation Description [https://leetcode.com/prob

小灰灰/ 2023年01月07日 08:46/ 0 赞/ 138 阅读

相关 [leetcode]268. Missing Number -- JavaScript 代码

/ @param {number[]} nums @return {number} / var missingNumber = function(nums)

雨点打透心脏的1/2处/ 2022年09月25日 06:20/ 0 赞/ 145 阅读

相关 268. Missing Number

268. Missing Number Given an array containing n distinct numbers taken from 0, 1, 2,

女爷i/ 2022年07月12日 11:53/ 0 赞/ 147 阅读

相关 268. Missing Number

268. Missing Number Given an array containing n distinct numbers taken from 0, 1, 2,

你的名字/ 2022年07月12日 11:53/ 0 赞/ 194 阅读

相关 [leetcode]: 268. Missing Number

1.题目 Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the

迈不过友情╰/ 2022年06月14日 23:20/ 0 赞/ 175 阅读

相关 268. Missing Number

/ 268. Missing Number Given an array containing n distinct numbers tak

╰半橙微兮°/ 2022年06月09日 03:55/ 0 赞/ 187 阅读

相关 LeetCode268. Missing Number解题

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that

雨点打透心脏的1/2处/ 2022年06月05日 05:35/ 0 赞/ 194 阅读

相关 268. Missing Number

给出一个包含 `0, 1, 2, ..., n` 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。 / Created by Joe on 20

r囧r小猫/ 2022年05月26日 22:58/ 0 赞/ 182 阅读

相关 leetcode-268 Missing Number

题目找到缺少的数字 Given an array containing n distinct numbers taken from 0, 1, 2, …, n, fi

落日映苍穹つ/ 2022年03月09日 14:39/ 0 赞/ 236 阅读

相关 leetcode_268.missing number

给定一个数组nums，其中包含0--n中的n个数，找到数组中没有出现的那个数。解法一：cyclic swapping algorithm class Soluti

ゝ一纸荒年。/ 2021年12月24日 14:45/ 0 赞/ 231 阅读