Cyclic Sort

[xiedaxia1hao]

287. Find the Duplicate Number 268. Missing Number 448. Find All Numbers Disappeared in an Array 645. 错误的集合 41. 缺失的第一个正数 765. 情侣牵手

循环排序

循环排序是一项重要的技巧。通常可以用来高效的解决一种未排序，元素值为 1-n 的数组（n为数组长度）。既然数组的元素都是其长度范围内的元素，如果这个数组排序，那么数组元素的值和其索引有着一一对应的关系。

例如数组 [3, 1, 2, 4, 5] 排序后是 [1, 2, 3, 4, 5]

arr[0] = 1 arr[1] = 2 arr[2] = 3 arr[3] = 4 arr[4] = 5

从排序后的数组可以看出，元素的的 值 == 索引 + 1。即元素都在其正确的位置上。如果元素不在其正确的位置上，那么这个元素可能是重复的数字，对应的索引可能就是缺失的数字。

因此通过循环排序可以解决leetcode 上类似寻找数组缺失数字，重复数字等问题。

那什么是循环排序呢？

循环排序的宗旨就是通过迭代数组，判断当前索引的元素是否在其正确的位置上。总结下来就两个步骤：

1. 迭代当前数组
2. 判断当前元素是否在其正确的索引位置，如果在则继续迭代，如果不在则与其正确索引位置的元素交换

其伪代码如下：

i = 0

while i < len(nums):
    j = get_next_index(nums[i])
    if nums[i] != nums[j]:
        nums[i], nums[j] = nums[j], nums[i]
    else:
        i += 1

结果这样处理，数组就"排序"好了，所谓排序指大部分元素都在其正确的索引位置，但是有些元素不在，这些元素可能是重复元素。

当我们把 我们给个随机的例子，让我们来对[4,3,2,7,8,2,3,1]来进行循环排序，该数组既存在重复数，也存在缺失数 :

[1, 2, 3, 4, **3**, **2**, 7, 8]

我们可以知道：

重复数：不在正确索引位置上的数 缺失数：不在正确索引位置上的数的索引+1

下面我们通过做真题来熟悉这个套路。

[xiedaxia1hao]

Cylic Sort模版

给定一个数组，其元素的值是 1 - n，n为数组的长度。每个元素都是unqiue。使用O(N)的复杂度原地排序 示例 1: 输入: [3, 1, 5, 4, 2] 输出: [1, 2, 3, 4, 5] 示例 2: 输入: [2, 6, 4, 3, 1, 5] 输出: [1, 2, 3, 4, 5, 6] 示例 3: 输入: [1, 5, 6, 4, 3, 2] 输出: [1, 2, 3, 4, 5, 6]

套用上面 cyclic sort 的模板，很容易写出下面的代码：

class CyclicSort {
  public static void sort(int[] nums) {
    int i = 0;
    while (i < nums.length) {
      int j = nums[i] - 1;
      if (nums[i] != nums[j])
        swap(nums, i, j);
      else
        i++;
    }
  }

  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

上述过程如图所示：

循环迭代数组的时候，当前元素的正确位置索引为其值 - 1。如果当前值不在正确位置，需要进行交换。直到其索引和值正确。这个过程中，i 并不会变化，即看起来有一个 内部 循环。那么时间复杂度是 O(N*N)吗？

实际上不是，因为每次交换，都有一个元素正确了，那么下次迭代到它的时候，自然也不用再交换。而处理当前元素的时候，最坏的情况下需要交互 N-1个元素。而剩下的元素都不用再交互，只有正常的迭代。最终复杂度是 O(N)+O(N−1) ，即线性复杂度。由于是原地排序，空间复杂度是 O(1)。

[xiedaxia1hao]

重复数

基于循环排序，如果数组的元素不是unique，有重复的元素，有一类题就是找出这些重复的数字。

287. Find the Duplicate Number

定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1: 输入: [1,3,4,2,2] 输出: 2
示例 2: 输入: [3,1,3,4,2] 输出: 3
说明： 不能更改原数组（假设数组是只读的）。 只能使用额外的 O(1) 的空间。 时间复杂度小于 O(n2) 。 数组中只有一个重复的数字，但它可能不止重复出现一次。

从题意保证输入只有一个重复的元素，并且符合循环排序的条件（元素是 1->n）。使用循环排序的技巧。那么就有元素不在其正确的索引位置上，这个元素就是重复的元素。

但是这样做其实不符合题意，因为题目说明要求不能改变原来的数组，cylic sort 会改变数组，这里使用 cylic sort 只是为了说明可以通过循环排序找出重复数。

class Solution {
    public int findDuplicate(int[] nums) {
        int i = 0; 
        while(i < nums.length) {
            int j = nums[i]-1;
            if(nums[i] != nums[j]) {
                swap(nums, i, j);
            } else {
                i++;
            }
        }

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

        return -1;
    }
}

这题正确的方法是用xor来做，比较基础，这边就不再过多阐述了。

[xiedaxia1hao]

缺失数

有元素重复了，那么重复的元素必然占据了其索引本来应该所在的元素。那么那个元素就是缺失的数字，另外一类题：

268. Missing Number

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            int j = nums[i]-1;
            if(nums[i] > 0 && nums[i] != nums[j]) {
                swap(nums, i, j);
            } else {
                i++;
            }
        }

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

        return 0;
    }

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

这题的关键是数组的元素包含 0，0 在这样的数组越界。对于越界的元素可以忽略不管。最后再找出这些索引位置不对的元素即可，类似的还有下面一题：

---

448. Find All Numbers Disappeared in an Array

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。 找到所有在 [1, n] 范围之间没有出现在数组中的数字。 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例: 输入: [4,3,2,7,8,2,3,1] 输出: [5,6]

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int i = 0;
        while(i < nums.length) {
            int j = nums[i]-1;
            if(nums[i] != nums[j]) {
                swap(nums, i, j);
            } else {
                i++;
            }
        }

        for(int k = 0; k < nums.length; k++) {
            if(nums[k] != k+1) {
                res.add(k+1);
            }
        }

        return res;
    }
}

[xiedaxia1hao]

通过上面的几道题，我们可以了解到循环排序通常找两类数：

• 重复数：不在正确索引位置上的数
• 缺失数：不在正确索引位置上的数的索引+1

关键都是找出不在正确位置上的数和其索引

下面一题正是将两者结合

645. 错误的集合

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。 给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1: 输入: nums = [1,2,2,4] 输出: [2,3]
注意: 给定数组的长度范围是 [2, 10000]。 给定的数组是无序的。

这题和上面所有题的套路都是一样的：

[nums[i], i+1] 正好是重复数和缺失数。时间复杂度依然是常数，也没有使用额外的空间。

class Solution {
    public int[] findErrorNums(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            int j = nums[i]-1;
            if(nums[i] == nums[j]) {
                i++;
            } else {
                swap(nums, i, j);
            }
        }

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

        return new int[]{-1, -1};
    }

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

[xiedaxia1hao]

越界处理

循环排序的重要条件就是数组元素范围在 1 - n内，就像上面第268题一样，有些问题的数组元素其实是会越界。当然，对于这种问题，也可以分析一下是否可以使用循环排序。

一个tips就是对于找缺失或者重复数，就可以尝试一下。

41. 缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1: 输入: [1,2,0] 输出: 3
示例 2: 输入: [3,4,-1,1] 输出: 2
示例 3: 输入: [7,8,9,11,12] 输出: 1
说明: 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

找出最小的正整数，按照循环排序的思路，对于越界的元素搁置不管。那么等"排序"结束后，错误位置的数字，那么就是目标要求的数。

需要注意的是，对于应排序好的全是正整数的数组，那么最终返回的值也会越界，即是 数组长度 + 1。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            int j = nums[i]-1;

            // CONSTAINTS: j >= 0 && j < nums.length
            // -> nums[i] - 1 >= 0 && nums[i] - 1 < nums.length
            // -> nums[i] >= 1 && nums[i] <= nums.length
            if(nums[i] >= 1 && nums[i] <= nums.length && nums[i] != nums[j]) {
                swap(nums, i, j);
            } else {
                i++;
            }
        }

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

        return nums.length+1;
    }

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

---

尽管这是一道 Hard 题目，通过循环排序的技巧，解题思路还是比较清晰。这种问题的还有一个变种，就是不再是找最小的正整数，而是找k个最小数。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            int j = nums[i]-1;

            // CONSTAINTS: j >= 0 && j < nums.length
            // -> nums[i] - 1 >= 0 && nums[i] - 1 < nums.length
            // -> nums[i] >= 1 && nums[i] <= nums.length
            if(nums[i] >= 1 && nums[i] <= nums.length && nums[i] != nums[j]) {
                swap(nums, i, j);
            } else {
                i++;
            }
        }

        List<Integer> missingNumbers = new ArrayList<>();
        Set<Integer> extraNumbers = new HashSet<>();
        for (i = 0; i < nums.length && missingNumbers.size() < k; i++) {
          if (nums[i] != i + 1) {
            missingNumbers.add(i + 1);
            extraNumbers.add(nums[i]);
          }
        }

        // add the remaining missing numbers
        for (i = 1; missingNumbers.size() < k; i++) {
          int candidateNumber = i + nums.length;
          // ignore if the array contains the candidate number
          if (!extraNumbers.contains(candidateNumber))
            missingNumbers.add(candidateNumber);
        }

        return missingNumbers;
    }

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

[xiedaxia1hao]

情侣牵手

循环排序的重要技巧是交换，交换之后能让部分元素的位置正确。通过交换来处理元素在leetcode还有一题，虽然标的不是循环排序，而是贪心算法。但是借用循环排序的交换元素的技巧，解题非常方便。

765. 情侣牵手

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。
这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
示例 1: 输入: row = [0, 2, 1, 3] 输出: 1 解释: 我们只需要交换row[1]和row[2]的位置即可。
示例 2: 输入: row = [3, 2, 0, 1] 输出: 0 解释: 无需交换座位，所有的情侣都已经可以手牵手了。
说明: len(row) 是偶数且数值在 [4, 60]范围内。 可以保证row 是序列 0...len(row)-1 的一个全排列。

从题意可知，判断两个元素是否是情侣可以通过定义得出，

2N-2 和 2N-1。N = (index // 2) + 1 但是这种相邻的数字，使用 ^异或求解更方便。

解题的思路就是使用贪心策略，假设当前的元素是正确的，那么就需要在剩余的元素中找到他的情侣。一旦找到，就处理好一对情侣，接着处理下一对，如果本身已经是正确的情侣，就直接跳过即可。代码如下：

class Solution {
    public int minSwapsCouples(int[] row) {
        int i = 0;
        int res = 0;

        while(i < row.length) {
            if(!isCouple(row[i], row[i+1])) {
                int j = i+1;
                while(j < row.length) {
                    if(isCouple(row[i], row[j])) {
                        swap(row, i+1, j);
                        res++;
                        break;
                    }
                    j++;
                }
            }
            i += 2;
        }

        return res;
    }

    public boolean isCouple(int i, int j) {
        return (i ^ 1) == j;
    }

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

[xiedaxia1hao]

总结

Cyclic Sort 模式的套路也比较清晰。大致2-3步，第一步迭代这个数组进行排序，第二步在处理当前元素的时候，判断其是否在其正确的索引位置，只要不是正确的位置就找到正确位置元素进行交换，最后一步就是再次迭代"排序"好的数组，找出不在正确索引位置的那个数和其索引，就是通常需要找的 重复数 和 缺失数。