首页 > 代码库 > LeetCode: missing num, count of 1s
LeetCode: missing num, count of 1s
Missing Number
[Problem]
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?
[Solution2] sum: Time~O(n) Space~O(1) //overflow risk
missing = expected_sum - actual_sum = (0+n)(n+1)/2 - sum
class Solution {public: int missingNumber(vector<int>& nums) { //sol1: actual_sum = 0+...+n = (0+n)*(n+1)/2 //missing = actual_sum - sum int n = nums.size(), sum = 0; for(auto num : nums) sum += num; return 0.5*n*(n+1) - sum; }};[Solution1] xor: Time~O(n) Space~O(1) //no overflow risk
xor all [i] and 0 to n: i^i=0, 0^missing=missing => final result = missing
[Tip]
- do not use for(auto...) since need to use counter "i"
- 0~n: n+1 numbers, nums[0~n-1]: n items => "for(i=0~n-1) res^=i^nums[i]" will not xor "n" => must init res=n
class Solution {public: int missingNumber(vector<int>& nums) { //sol2: xor all items and 0~n => (i^i)=0 so 0^missing=missing int n = nums.size(), res = n; for(int i=0; i<n; ++i) res ^= i ^ nums[i]; return res; }};
LeetCode: missing num, count of 1s
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。