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. OK, I Understand
 
Top