## Wednesday, November 2, 2016

### LeetCode 448 - Find All Numbers Disappeared in an Array

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
```Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]
```
https://discuss.leetcode.com/topic/65738/java-accepted-simple-solution
1. Negate each number while traversing
2. Run again and find the index that is not negated.
The basic idea is that we iterate through the input array and mark elements as negative using `nums[nums[i] -1] = -nums[nums[i]-1]`. In this way all the numbers that we have seen will be marked as negative. In the second iteration, if a value is not marked as negative, it implies we have never seen that index before, so just add it to the return list.
``````    public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> ret = new ArrayList<Integer>();

for(int i = 0; i < nums.length; i++) {
int val = Math.abs(nums[i]) - 1;
if(nums[val] > 0) {
nums[val] = -nums[val];
}
}

for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) {
}
}
return ret;
}``````

def findDisappearedNumbers(self, nums): """ :type nums: List[int] :rtype: List[int] """ for n in nums: nums[abs(n) - 1] = -abs(nums[abs(n) - 1]) return [i + 1 for i, n in enumerate(nums) if n > 0]

https://discuss.leetcode.com/topic/66581/simple-java-in-place-sort-solution
The idea is simple, if nums[i] != i + 1 and nums[i] != nums[nums[i] - 1], then we swap nums[i] with nums[nums[i] - 1], for example, nums[0] = 4 and nums[3] = 7, then we swap nums[0] with nums[3]. So In the end the array will be sorted and if nums[i] != i + 1, then i + 1 is missing.
The example run as follows
``````[4,3,2,7,8,2,3,1]
[7,3,2,4,8,2,3,1]
[3,3,2,4,8,2,7,1]
[2,3,3,4,8,2,7,1]
[3,2,3,4,8,2,7,1]
[3,2,3,4,1,2,7,8]
[1,2,3,4,3,2,7,8]
``````
Since every swap we put at least one number to its correct position, the time is O(n)
``````    public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
int tmp = nums[i];
nums[i] = nums[tmp - 1];
nums[tmp - 1] = tmp;
}
}
List<Integer> res = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
}
}
return res;
}``````
https://discuss.leetcode.com/topic/66063/5-line-java-easy-understanding
``````public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < nums.length; i ++) nums[(nums[i]-1) % n] += n;
for (int i = 0; i < nums.length; i ++) if (nums[i] <= n) res.add(i+1);
return res;
}``````

RELATED:
http://www.cnblogs.com/grandyang/p/4756677.html
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`.

```    int missingNumber(vector<int>& nums) {
int sum = 0, n = nums.size();
for (auto &a : nums) {
sum += a; // USE LONG FOR SUM
}
return 0.5 * n * (n + 1) - sum;
}```
```    int missingNumber(vector<int>& nums) {
int res = 0;
for (int i = 0; i < nums.size(); ++i) {
res ^= (i + 1) ^ nums[i];
}
return res;
}```

```    int missingNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > mid) right = mid;
else left = mid + 1;
}
return right;
}```