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

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

### [ Move Zeros](https://leetcode.com/problems/move-zeroes/)

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

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

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

```java
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)

```java
    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](https://leetcode.com/problems/missing-number/)

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

```java
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](https://leetcode.com/problems/first-missing-positive/)

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

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

#### 注意要点：

* **当前元素的目标位置 index 有可能越上下界，多加两个判断条件；**
* **如果真是 swap 了，不代表当前元素一定是正确位置，指针不要动(或者说在 for loop 里面要 i--)**

```java
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](https://leetcode.com/problems/missing-ranges/)

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

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

```java
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](https://leetcode.com/problems/find-the-duplicate-number/)

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

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

```java
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]]，不然死循环。

```java
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 = 最小公倍数


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/missing_number_lei.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.