程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode] Missing Number

[LeetCode] Missing Number

編輯:關於C++

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?

解題思路

思路1:0-n求和,再減去數組元素的總和,即為缺失元素。
思路2:亦或操作。兩個相同的數亦或結果為0,一個不為0的數與0亦或,其值為本身。

實現代碼

C++代碼1:

// Runtime: 36 ms
// 代碼已AC,但求和有溢出風險。
class Solution {
public:
    int missingNumber(vector& nums) {
        int len = nums.size();
        int sum = 0;
        for_each(nums.begin(), nums.end(), [&sum](int n){ sum += n; });
        int total = (len + 1) / 2.0 * (0 + len);
        return total - sum;
    }
};

C++代碼2:

// Runtime: 36 ms
class Solution {
public:
    int missingNumber(vector& nums) {
        int miss = nums[0] ^ 0;
        for (int i = 1; i < nums.size(); i++) {
            miss ^= nums[i];
            miss ^= i;
        }

        return miss ^= nums.size();
    }
};

Java代碼1:

// Runtime: 1 ms
public class Solution {
    public int missingNumber(int[] nums) {
        int sum = (int)((nums.length + 1) / 2.0 * nums.length);
        for (int n : nums) {
            sum -= n;
        }

        return sum;
    }
}

Java代碼2:

// Runtime: 1 ms
public class Solution {
    public int missingNumber(int[] nums) {
        int miss = nums[0] ^ 0;
        for (int i = 1; i < nums.length; i++) {
            miss ^= nums[i];
            miss ^= i;
        }

        return miss ^= nums.length;
    }
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved