283. Move Zeros

FB 的超高频

这种写法中，我们调用 swap 的次数取决于从数组第一个 0 开始，后面到底有多少个非 0 元素。

一次 swap = 2次数组写入 + 1次 temp variable 写入，总写入次数为 O(3n)，总数组写入次数为 O(2n)

public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;

        int i = 0;
        while (i < nums.length && nums[i] != 0) i++;
        for (int j = i + 1; j < nums.length; ++j) {
            if (nums[j] != 0) swap(nums, i++, j);
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

然后 follow-up 肯定是如何减少写入次数 (aka 别用 swap)

这个时候解法就有点像27了，不为目标值的时候（这道题目标值为0），我们把当前值覆盖到前面，从头开始覆盖，不用管被覆盖的值是多少，因为我们只关心最后的结果。

和27不太一样的是，最后要再把0写回去，当然操作是很trivial的。

其实我觉得这个写法才是最直观的，暴力点用 swap 的写法反而 tricky 一点

这种写法中，数组每一个位置一定会被不多不少写入一次，写入次数为 O(n)

public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;

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

287. Find the Duplicate Number

public class Solution {
    public int findDuplicate(int[] nums) {
        if (nums.length > 1) {
            int slow = nums[0];
            int fast = nums[nums[0]];

            while (fast != slow) {
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            fast = 0;
            while (fast != slow) {
                fast = nums[fast];
                slow = nums[slow];
            }
            return slow;
        }
        return -1;
    }
}

41. First Missing Positive

Pocket Gems 电面题库

这题真的垃圾，到现在也是记的答案。

思路就是不断试图把当前元素替换到其正确的位置上；如果目标位置元素已经正确则 do nothing，如果目标位置越界，也 do nothing. 每次交换之后指针位置不动，继续试图新一轮替换。这样一次循环之后，所有能被放到正确位置的元素，都会被放过去，而第一个位置和值不匹配的元素就是我们要寻找的目标。

注意要点：

• 当前元素的目标位置 index 有可能越上下界，多加两个判断条件；

• 如果真是 swap 了，不代表当前元素一定是正确位置，指针不要动(或者说在 for loop 里面要 i--)

public class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != i + 1 && nums[i] - 1 >= 0 &&
               nums[i] - 1 < nums.length && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
                i--;
            }
        }
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        return nums.length + 1;
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}