第一次写算法题解，算是新的尝试，前几个月的题解都在力扣里，好处是有很多测试用例，坏处是你写题解不太方便，我的很多解法和注释都在代码里面里。 正好在别的地方看到里这个题目但是在力扣里没找到，所以不仅要写解法，还需要写测试用例，挺有趣的。 原题来自

https://me.guanghechen.com/post/quiz/partition/find-duplicate-number/#footnote-2

PS: 这个博客效果是炫，太费 CPU了，我还是喜欢简洁些的image-20210810122800858

题目

给定一个长度为 N+1 的数列 A={a0,a1,a2⋯,aN}. 其中 1⩽ai⩽N,0⩽i⩽N,N⩾1.

在满足以下限制的前提下找出数组中任意一个重复的数字：不能修改输入的数组；只能使用 O(1) 的额外空间

这个题目的条件是精心挑选的，我理解为是为了算法而特意设定的约束条件。比方说

  1. 数组长度说 N + 1，而不是 N
  2. 数组里不包含 0
  3. 找到任意一个，而不是全部

所以简化下理解，数组里包含里一个从 1 ～ N 的自然序列，额外再加一个 1 ～ N 的数字。

解法

如果没有最后一个约束条件，我们有一个暴力算法，通常我不会做的题目我都会先去掉一些条件来看最差的实现方式，从而理解题目里的考察点。

暴力算法

其一、不借助额外的空间,符合题目描述，但是时间复杂度高 o(n^2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// https://www.acwing.com/problem/content/description/15/
// var nums = [2, 3, 5, 4, 3, 2, 6, 7];
function forceFindDuplicate(_arr) {
  // 第一种解法，能找出所有的数字；
  // 算法是 时间复杂度 o(n^2)，空间是 o(1)
  for (let i = 0; i < _arr.length; i++) {
    const d1 = _arr[i];
    for (let j = 0; j < _arr.length; j++) {
      if (i == j) {
        continue;
      }
      const d2 = _arr[j];
      if (d1 === d2) {
        return d1; // 找到一个就退出
      }
    }
  }

  return -1;
}

这个算法的优点是没有使用额外空间；而且稍微改造下就可以找到所有的重复数组。

其二，借助一个辅助空间，空间复杂度 o(n).

主要思路是，初始化一个 map 遍历一遍数组，然后以 value 为 key，遍历到某个元素时，先检查 map 是否存在此 value，有则说明已经重复了，没有把本 value 保存到 map。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function findDuplicateWithMap(nums){
  let cache = {};
  for(var i = 0;i < nums.length; i++){
    let v = nums[i];
    if (cache[v]) return v;
    // 保存到 cache 里
    cache[v] = 1;
  }
  return -1;// 表示没有找到
}

以上是我自己脑瓜子能想出来的，下面就是算法网站的标准答案，我按照自己的理解加上注释，以为能变成我自己的理解，后面可以举一反三。

分治法

分治法说起来简单，实际上本题目能用分治有以下的前提条件

  1. 题目数量 N+1，保证了所有数字都应该出现，而且有一个额外的数字和现有的数字重合。所以可以使用鸽笼原理
  2. 不需要找到所有重复的

主要的思路是：

  • 当所有值都存在于 1 ～ n 时，如果没有重复，则 小于等于 n 值的数量一定和 n 值本身是一致的；
  • 如果 小于等于 n 值的数量大于 n 本身，说明其中有一个被多算了一次；
  • 如果少，则说明在另外一个区间，而且另外一个区间不包括 n；
  • 所以本算法的目的是去找具体的值，而不是去找下标，不要习惯性的去找下标。这点很重要，因为通常数组的算法都是去操作下标
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

 function divideAndConquer(_arr) {
    let l = 1, h = _arr.length - 1;// 为什么 -1，因为题目里说了 n+1 长度的数组；
    for (; l < h;) {

        var m = (l + h) >> 1;
        var count = 0;
        _arr.forEach(d => {
            if (d <= m && d >= l) {
                count++;
            }
        });
        if (count > (m - l + 1)) {
            // 在低部位取值，这个条件连 =m （见上面）都判断了
            h = m;
        } else {
            // 不在底部，包括M，那么下一次就从 m+1 开始
            l = m + 1;// 
        }
    }
    return l;// 此时 l = h
}

带环链表

想到数组里带重复的项目，可以理解为链表里带有环，而本题目转化为如何求解环，已经如何确认环的入口位置。 但我们不能直接像其他文章里那样直接进行第二步——环监测，第三部——环的定位。我们需要确认如何把数组转化为链表。

第一步，把数组转化为链接 我在这一步里走来弯路，最开始的想法是数组第一个作为 head，它的值指向下一个下标，但是考虑到数组里没有 0，所以对每个值都做里-1 操作。以下是错误示范

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

function loopCheck(_arr) {
    // 把数组当作链表，重复可以理解为一种环，所以这个问题就当作如何做环监测
    // 把数组里的值作为 next_pointer,下标 index 当作 pointer
    // 而是把值作为 pointer，遍历数组生成链表。
    // 如果检查该项都 val 是否已经被创建，如果创建了，说明有环，如果没有继续添加到链表后面
    var head = 1;
    var total = 40;
    var fast = head, slow = head

    while (total-- > 0) {
        slow = _arr[slow - 1]

        var fastValue1 = _arr[fast - 1];
        fast = _arr[fastValue1 - 1];

        console.log(`Slow = ${slow}, fast = ${fastValue1} -> ${_arr[fast - 1]}`)
    }

}

上面代码是为了演示如何把数组当列表遍历，但是遇到 [1, 2, 5, 4, 3, 2, 6, 7]，这样测试用例的时候出现死循环，nums[1-1]=1。然后我就换思路里，变成了数组的相邻当作指针的指向，每一步都检查 val 是否存在（不贴代码了）。其实大部分的思路是对的，就是不应该对 x - 1；还有不应该顾虑

1

nums[x] = x

这样的死循环。它其实是一种合理的终止条件，那说明一定有一个项指向了 x，即

1

nums[y] = x

意味着 y=x。而初始条件 nums[0] 绝对不会 = 0，意味着不会 x = 0，即

1

nums[x] = x ; x > 0;

不会在第一步就产生死循环，一定会至少一次的指针跳转。而且因为 ai > 0，所以不会再次访问数组第一项。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

function loopCheck2(nums) {
    // 上面的实现立还是引入了额外的 ListNode，和 cache 都不符合要求，是否可以进一步简化

    // 照抄了参考链接的代码
    // 经过研究得知，这个算法可行有两个前提，
    // 1. 第一不存在 0 值，这样避免第一步就原地打转，无法前进，不走第二步就不会有相同元素的说法；
    // 2. 而且因为数组里的值永远不会= 0，所以必须从 0 开始；
    // 2. 和最开始想的一样： 每个元素的值是下标，相当于 pointer，默认 pointer 第一个即 index = 0；

    var x = 0, y = 0;
    // 形如 [2, 3, 2, 3, 1] 这样，一旦进入循环就会导致死循环的数组，可以说明一点：
    // 如果 x = nums[x], 则表明一定有另外的一个元素的值 = x，才会指向 x的。此时已经是一个环了。
    while (x == 0 || x != y) {
        var t = nums[x];
        x = nums[t];
        y = nums[y];
        console.log(`slow = ${y}, fast = ${t} -> ${x}`)
    }
    // 此时 y = x，确定的是 y 一定是在环上。
    for (x = 0; x != y;) {
        x = nums[x];
        y = nums[y];
        console.log(`slow = ${y}, fast =  ${x}`)
    }

    return x;
}

证明

虽然得知了结果，但是现在需要证明的是

  1. 为何用快慢指针终究会相遇；
  2. 如何确保定位到环之后，从新出发的指针能和老指针回合在

在纸上证明了（还在学如何在 html 里载入图示，待补充）。f 表示快指针、 s 表示慢指针、q 是直线部分，p 是环大小

  • 快慢指针一定会相遇。 则当 s 进入环入口时， $$ d = f - s = 2p - q / p - q$$ 那么还需要 d 步两个指针就能相遇（意味着 value 相同）
  • 如何确认环的入口 q > p 时，以慢指针进入环后相遇的位置为 2p - q，那么说明此时还需要再走 q 才算环都闭合。如果此时，第二个慢指针走 p 步，恰好相遇； q < p 时，同理还更简单。

变形题目求解

给定一个长度为 N+1 的数列 A={a0,a1,a2⋯,aN}. 其中 1⩽ai⩽N,0⩽i⩽N,N⩾1.

在满足以下限制的前提下找出数组中任意一个重复的数字：不能修改输入的数组；只能使用 O(1) 的额外空间

额外条件，只有一个数字是重复，如何求解？

总和减去等差数列之和
全选文本查看。

测试代码的代码

（跑测试集合）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

var testcases = [
    {
        t: [2, 3, 5, 4, 3, 2, 6, 7],
        a: [2, 3]
    },
    {
        t: [1, 2, 5, 4, 3, 2, 6, 7],
        a: [2]
    },
    {
        t: [1, 2, 5, 4, 3, 2, 6, 1],
        a: [1, 2]
    },
    {
        t: [7, 1, 5, 4, 3, 2, 6, 6],
        a: [6]
    },
    {
        t: [3, 7, 5, 4, 4, 2, 6, 1],
        a: [4]
    },
    {
        t: [10, 13, 17, 6, 13, 10, 16, 3, 12, 2, 18, 18, 16, 15, 7, 1, 3, 10, 9, 14],
        a: [10, 13, 16, 3]
    },
    {
        t: [20, 19, 18, 16, 15, 12, 10, 6, 5, 11, 4, 2, 1, 3, 7, 8, 9, 11, 13, 14, 17],
        a: [11]
    },
    {
        t: [80, 78, 76, 74, 71, 70, 67, 65, 64, 61, 56, 55, 54, 53, 51, 41, 24, 39, 37, 35, 34, 30, 29, 27, 26, 25, 23, 21, 18, 16, 15, 14, 12, 10, 9, 4, 2, 1, 3, 5, 6, 7, 8, 11, 13, 17, 19, 20, 22, 24, 28, 31, 32, 33, 36, 38, 40, 42, 43, 44, 45, 46, 47, 48, 49, 50, 52, 57, 58, 59, 60, 62, 63, 66, 68, 69, 72, 73, 75, 77, 79],
        a: [24]
    }
];

function run(targetFunc) {
    var ok = true;
    testcases.forEach(tc => {
        var t = tc.t, a = tc.a;
        var r = targetFunc(t)
        if (a.indexOf(r) > -1) {
            console.log(`done with ${t}`)
        } else {
            var e = new Error(`failed, expect ${a}, got ${r}`)
            console.log(e);
            console.log(t);
            return -1;
        }
    });
    return 0;
}

这个题目陆陆续续我大概做了 2 天，其实还是学了很多。

参考

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

EOF