Missing Number 类，元素交换，数组环形跳转

Move Zeros

FB 的超高频，记得先演一演，给个 swap 的写法~

这种写法中，我们调用 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 ptr = 0;
        while(ptr < nums.length && nums[ptr] != 0) ptr ++;
        for(int i = ptr + 1; i < nums.length; i++){
            if(nums[i] != 0) swap(nums, i, ptr++);
        }
    }

    private void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

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

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

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

    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;
        }
    }

Missing Number

等差数列。英文叫 arithmetic sequence，记一下，和老外面试官吹比用。。

public class Solution {
    public int missingNumber(int[] nums) {
        int N = nums.length;
        int sum = 0;
        for(int num : nums) sum += num;
        return  (N + 1) * N / 2 - sum;
    }
}

First Missing Positive

这题挺 tricky 的，到现在也是记的九章的答案。

思路就是不断试图把当前元素替换到其正确的位置上；如果目标位置元素已经正确则 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 a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

Missing Ranges

研究区间类问题的时候做过一次，挺有意思的。

这题的要点在于 “不断更新 lower”，并且根据个新元素带来的区间终点决定是添加一个元素，还是一个区间。

public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> list = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            int candidate = nums[i] - 1;

            if(candidate == lower) list.add("" + candidate);
            else if(candidate > lower) list.add("" + lower + "->" + candidate);

            lower = Math.max(lower, nums[i] + 1);
        }

        if(lower == upper) list.add("" + lower);
        else if(lower < upper) list.add("" + lower + "->" + upper);

        return list;
    }
}

Find the Duplicate Number

这题是一个道理，我们依然用 first missing positive 的做法，把每个数试图换到它对应的位置上；然后 nums 数组最后的那个元素，一定是 duplicate element，因为其他元素都归位之后，它没地方去。因为如果最后一个元素是唯一元素的话，它一定会被置换到正确位置上。

好吧，写完了我才发现不让修改原数组= =

public class Solution {
    public int findDuplicate(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--;
            }
        }

        return nums[nums.length - 1];
    }

    private void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

这题还有另一种很妖孽的写法，就是把它当成 LinkedList 做。。

https://discuss.leetcode.com/topic/25913/my-easy-understood-solution-with-o-n-time-and-o-1-space-without-modifying-the-array-with-clear-explanation

那么这道题又跟Find the Duplicate Number有什么关系呢？在table中每个元素存储的是table index，根据其跳转，其实就是把table中的元素作为指针来使用。就像我们在上题中也是在child node中存parent node的index，并做跳转。我们结合Find the Duplicate Number这道题来看。这道题讨论区most voted的解法即是一个国人大神把它转化为了Linked List Cycle来做。 find linked list cycle是一道大家都很熟悉的题。而国人大神的解法就是把given array中的每一个元素当作指针来用跳转到下一个元素。我们用A[1, 4, 3, 2, 5, 2, 6]来做例：

当我们扫到A[0]时，A[0] == 1，把它作为指针来使用，我们跳到A[1];

A[1] == 4, 跳到A[4];

A[4] == 5, 跳到A[5];

A[5] == 2, 跳到A[2];

A[2] == 3, 跳到A[3];

A[3] == 2, 开始循环...

这道题之所以可以把元素作为指针来使用当然也是题干出的巧。

这里要注意初始化问题，fast 要初始化成 nums[nums[0]]，不然死循环。

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

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

(G面经)

然后是一道关于按照固定的顺序重新排序，多少次排序才能回到初始顺序的题目，我们总是把第x个位置的元素移到第y个位置，比如【0，1，2，3】就是完全不换顺序，一次排序就回去了；【3，2，1，0】是位置3和位置0互换，位置2和位置1互换，两次排序就能回到原顺序；而【1，2，3，0】就是每次把一个位置上的元素往后移动一个位置，那显然转一圈就回来了。

举个例子，原来的input为[20, 34, 7, 9], 排序要求为[1, 3, 2, 0] 一次排序后： [20, 34, 7, 9] -> [34, 9, 7, 20] 二次排序后: [34, 9, 7, 20] -> [9, 20, 7, 34] 三次排序后： [9, 20, 7, 34] -> [20, 34, 7, 9] (此时和初始顺序一致，所以是用了三个iteration恢复原样)

排序规则[1, 3, 2, 0]的意思是把在位置1的元素排到第0个位置，位置3的元素排到第2个位置，位置2的元素还是在位置2，位置0的元素放到位置3去。排序规则不变，每次只是Input被按照规则改变了顺序。

这个小技巧也可以用在原帖第二轮第二题上。

原帖中Heliuhun对于这道题给了一个很精妙的解法。我们来分析一下这个解法。用A[a1, a2, a3, a4, a5], B[1,0,4,2,3]做例: 我们并不在乎A中的每个数到底是什么。我们想知道的是A中的每个数按照B来移动，最少经过多少次可以回到原位。对于a2来说，它经历一次移动从1来到了0的位置。再经历一次移动从0回到了1的位置。对于a4来说，它经历一次移动从3来到了2的位置。再经历一次移动从2来到了4的位置。再经历一次移动从4回到了3的位置。可以看到A中的元素是根据B来跳转的，并且把B中的元素当作指针来使用。B中的元素形成了一个或多个封闭的环状“linked list”。按照Heliuhun的思路，我们需要找出B中有多少封闭的环状“linked list”，再找出它们的最小公倍数。为什么是最小公倍数呢？拿上面的例子来说，当a2经过两次移动后回到原位时，a4还需要一次移动才能回到原位。最少经过6次移动，a2，a4以及a1，a3，a5才能同时回到原位。

跳转序列可以拆成几个独立的环，同时也知道每个环的长度，然后求所有环长度的最小公倍数？比如[1,0,4,2,3]就是0-1-0 和 2-3-4-2两个环，所以6次shuffle后变回原来的数组

Least common multiple = 最小公倍数

PreviousFrequency 类问题 Next8/10, Google Tag

Last updated 3 years ago