• API
• FAQ
• Tools
• Archive
daily pastebin goal
47%
SHARE
TWEET

# Untitled

a guest Mar 26th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2. Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
3.
4. For example,
5. Given nums = [0, 1, 3] return 2.
6.
7. Note:
8. Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
9.
10. Credits:
11.  */
12.
13. /*
14.  * 本题要找出 0...n 中缺少的数，使用位运算的效率最高
15.  * 使 res 异或 0...n 中的每个数，再异或 nums 向量中的每个数
16.  * 异或两次不修改原值，仅异或一次的数被留在 res 中
17.  */
18.
19. class Solution {
20. public:
21.     int missingNumber(vector<int>& nums) {
22.         int i = 0;
23.         int res = nums.size();
24.         for (auto num : nums)
25.         {
26.             res ^= num;
27.             res ^= (i++);
28.         }
29.         return res;
30.     }
31. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top