Missing Number, find duplicate

Move Zeroes

FB高频题，写入次数（Write times）

Analysis

展示如何一步一步去优化整个算法

The most naive approach should be extremely straightforward. By keeping two arrays: one for non-zero numbers and one for all zeroes, we can concatenate them at the end. Since we just need to traverse the array once, this will give us O(N) time complexity. Space complexity is O(N) as we need two additional arrays.

Apparently, time complexity can’t be improved as we need to traverse the array at least once. In order to use less space, we should look for modifying the array.

// 先演一演，展示一个swap的做法，找到第一个0，然后和后面非0的元素进行swap
// 一次 swap = 2次数组写入 + 1次 temp 写入，总写入次数为 O(3n)，总数组写入次数为 O(2n).
// 
// [0, 1, 0, 3, 12]
public class Solution {
    public void moveZeroes(int[] nums) {
        int p0 = 0;
        int n = nums.length;
        // p0寻找为0的位置
        while(p0 < n && p0 != 0) p0++;
        for(int i = p0 + 1; i < nums.length; i++) {
            if(nums[i] != 0) {
                swap(nums, p0++, i);
            }
        }
    }

    public void swap (int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

然后 follow-up 肯定是如何减少写入次数 (aka 别用 swap)，后面的演技就是这样……

其实我一直觉得这个写法才是最直观的，暴力点用 swap 的写法反而 tricky 一点。。 这种写法中，数组每一个位置一定会被不多不少写入一次，写入次数为 O(n)

双指针法，一个track当前有效数组的长度，一个去找非0的数，然后覆盖

Quick sort的partition思想

public void moveZeroes(int[] nums) {
    // i维护的是有效数组的长度
    int i = 0, j = 0;
    int n = nums.length;
    while(j < n) {
        if (nums[j] != 0) {
            nums[i++] = nums[j];
        }
        j++;
    }
    while(i < n) {
        nums[i++] = 0;
    }
}

Find duplicate number

Given an array of n elements，已知所有elements都在1 - n里面， 并且有只有一个数字missing，一个数字duplicate。 return那个duplicate。 Linear time，constant space

Example：［1，3，4，3］return 3

因为每个element和index都是一一对应的关系，所以我们可以通过不断的交换，让每一个element都回到应该在的位置上。一旦我们发现有两个位置都对应着同一个element的时候，说明这个元素是重复的。

public static int findDupNumber(int[] nums) {
    int i = 0;
    while(i < nums.length) {
        while (nums[i] - 1 != i) {
            if (nums[nums[i] - 1] == nums[i]) {
                // find dup
                return nums[i];
            } else {
                swap(nums, nums[i] - 1, i);
            }
        }
        i++;
    }
    return -1;
}

First Missing Positive

找到第一个不能正确对应到自己位置上的正整数。

首先0不是正整数，所以正确的对应顺序应该是

0 -> 1 1 -> 2 2 -> 3

第一想法是先排序，然后从1开始找第一个不连续的数。

更快的方法就是用一个HashSet，把所有的数加进去，然后再从1往length，开始找第一个不连续的。

还有一个更省空间的做法：就是位置映射法，把每个数都swap回自己正确的位置上.

public class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 1;
        }

        for(int i = 0; i < nums.length; i++) {
            // 1 ~ n
            if(nums[i] <= nums.length && nums[i] > 0 && nums[nums[i] - 1] != nums[i]) {
                // 如果不合法，放到自己正确的位置上，也就是index = nums[i] - 1
                swap(nums, nums[i] - 1, i);
                i--;
            }
        }

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != i + 1) {
                return i + 1;
            }
        }

        return nums.length + 1;
    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

Find the Duplicate Number

You must not modify the array (assume the array is read only). 所以不能swap，不能排序。

You must use only constant, O(1) extra space. 不能用hashset

Your runtime complexity should be less than O(n2). 不能two for-loop

There is only one duplicate number in the array, but it could be repeated more than once.

鸽巢法，二分法

实际上，我们可以根据抽屉原理简化刚才的暴力法。我们不一定要依次选择数，然后看是否有这个数的重复数，我们可以用二分法先选取n/2，按照抽屉原理，整个数组中如果小于等于n/2的数的数量大于n/2，说明1到n/2这个区间是肯定有重复数字的。比如6个抽屉，如果有7个袜子要放到抽屉里，那肯定有一个抽屉至少两个袜子。这里抽屉就是1到n/2的每一个数，而袜子就是整个数组中小于等于n/2的那些数。这样我们就能知道下次选择的数的范围，如果1到n/2区间内肯定有重复数字，则下次在1到n/2范围内找，否则在n/2到n范围内找。下次找的时候，还是找一半。

public int findDuplicate(int[] nums) {
    // index range from 0 ~ (n - 1)
    int start = 0;
    int end = nums.length - 1;

    while(start <= end) {
        int mid = (start + end) / 2;
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] <= mid) {
                count++;
            }
        }
        if(count > mid) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return start;
}

映射找环法 O(N)

index 范围是 0 ~ n 数值 范围是 1 ~ n

从0开始，把每个index对应的数值作为一个新的index 组成一个链表的形式，当这个链表开始有环的地方就是那个duplicate的元素。我们需要做的就是找到这个环的入口。

所以这一题的解法就和linked list cycle II 一样了。

public int findDuplicate(int[] nums) {
    int walker = 0;
    int runner = 0;

    do {
        walker = nums[walker];
        runner = nums[nums[runner]];
    } while (walker != runner);

    int find = 0;

    while (find != runner) {
        find = nums[find];
        runner = nums[runner];
    }

    return find;
}