不修改数组找出重复的数字

问题描述
¶

给定一个长度为 $N + 1$ 的数列 $A = {a_{0}, a_{1}, a_{2} \dots, a_{N}}$ .
其中 $1 ⩽ a_{i} ⩽ N, 0 ⩽ i ⩽ N, N ⩾ 1$ .

在满足以下限制的前提下找出数组中任意一个重复的数字：

不能修改输入的数组；
只能使用 $O (1)$ 的额外空间；

分治法
¶

分治算法的思想是不断收紧区间范围以确定重复的数字其值所在的区间范围，当区间长度为 $1$ 时，则找到了那个重复的数字（相当于二分答案）。

算法描述
¶

根据鸽巢原理易知，原数组中必然至少有一个重复的数字，即答案所在区间为 $[1, N]$ 。不妨取 $x = ⌊ \frac{1 + N}{2} ⌋$ ，则要么有 $x + 1$ 个数的值落在区间 $[1, x]$ 中，要么有 $N - x$ 个值落在区间 $[x + 1, N)$ 中 ^[1]。这样，我们就把重复数字所在区间的长度缩减了一半了。重复操作，直到区间长度为 $1$ .

程序实现
¶

时间复杂度： $O (N \log N)$
空间复杂度（额外）： $O (1)$

分治法.cpp | 15 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int duplicateInArray(std::vector<int>& nums) {
  int L = 1, R = nums.size() - 1;
  for (int M, cnt; L < R;) {
    M = (L + R) >> 1;
    cnt = 0;
    for (int x : nums) {
      if (x >= L && x <= M) cnt += 1;
    }
    if (cnt > (M - L + 1))
      R = M;
    else
      L = M + 1;
  }
  return L;
}

追击法
¶

前置知识
¶

如何判断一个链表有环呢？
采用双指针遍历链表，快指针每次走两步，慢指针每次走一步，若链表中存在环，则快指针一定能追上慢指针 ^[2]。
因为至多在环内多跑一圈就可以追上慢指针，所以算法复杂度为：
- 时间复杂度： $O (N)$
- 空间复杂度： $O (1)$
若链表中存在环，如何找到环的入口呢？
因为快指针（不妨记为 $x$ ）的速度是慢指针（不妨记为 $y$ ）的两倍，因此当慢指针在环内未走完一圈时就会被快指针追上 ^[3]。不妨假设从出发位置到达环的起点的距离是 $d_{0}$ 步，从相遇位置出发再走 $d_{1}$ 步首次到达环的起始点，环的长度为 $l$ ，则有：
$\begin{aligned} d_{0} + k_{x} \cdot l - d_{1} = 2 (d_{0} + k_{y} \cdot l - d_{1}) \\ \Rightarrow & k_{x} \cdot l = d_{0} + 2 k_{y} \cdot l - d_{1} \\ \Rightarrow & d_{1} = d_{0} + (k_{x} - 2 k_{y}) \cdot l \end{aligned}$
其中 $k_{x}, k_{y}$ 为正整数，分表表示快指针和慢指针走的圈数 $+ 1$ （根据前面的分析，我们知道此处 $k_{y} = 1$ ，虽然这对算法并没有影响）。观察上式可以发现，若慢指针再行走 $d_{0}$ 步，即可到达环的起点。这给了我们一个启发，即当慢指针和快指针相遇时，我们再放一个新的慢指针 $z$ 让它从链表起点出发，在它走到环的起点时，恰好走了 $d_{0}$ 步，并与慢指针 $x$ 相遇。
综上，我们仅需在快指针和慢指针相遇时，放一个新的慢指针从链表起点出发，当两个慢指针相遇时，即到达环的入口。
因为在找到环的基础上至多走 $d_{0}$ 步，所以算法复杂度为：
- 时间复杂度： $O (N)$
- 空间复杂度： $O (1)$

算法描述
¶

因为原题中的数列的数值范围在 $[1, N]$ 之间，而这些值都属于原数列的有效下标，因此不妨假设原数组描述的是一个下标指向值的链表，即 $i \to a_{i}$ ，下一步再将 $a_{i}$ 看做新的位置，指向 $a_{a_{i}}$ ，以此类推。

不难发现这个链表中一定存在环，因为若不存在环，且走过了 $k$ 个位置，则这 $k$ 个位置对应的数值必然不相同 ^[4]，则最后一个数字会指向一个新的下标，直到空间 $[1, N]$ 内的所有下标都被消耗完。而因为总共有 $N + 1$ 个数却只有 $N$ 个下标，根据鸽巢原理可知，必然至少有一个下标会被重复使用。

根据前面的分析，不难有：

从任意位置出发，都必然到达环；
环的起始位置对应的数值即为原问题中的重复的数；

不妨从位置 $0$ 出发，假设从 $a_{x}$ 位置进入环，则环内必然存在一个位置 $j$ ，满足 $a_{j} = a_{x}$ ，即环的入口处是原数列中的一个重复数字：

剩下的问题按照前文求链表的入口的算法求解即可，此处不再赘述。

程序实现
¶

时间复杂度： $O (N)$
空间复杂度（额外）： $O (1)$

追击法.cpp | 15 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int duplicateInArray(std::vector<int>& nums) {
  int x = 0, y = 0;

  while (x == 0 || x != y) {
    x = nums[nums[x]];
    y = nums[y];
  }

  for (x = 0; x != y;) {
    x = nums[x];
    y = nums[y];
  }

  return x;
}

问题描述¶

分治法¶

算法描述¶

程序实现¶

追击法¶

前置知识¶

算法描述¶

程序实现¶

Related¶

问题描述
¶

分治法
¶

算法描述
¶

程序实现
¶

追击法
¶

前置知识
¶

算法描述
¶

程序实现
¶

Related
¶