寻找数组中的重复数字

前言

前面一系列文章分享了数据结构与算法的基础知识，接下来分享一些算法题的解题思路与实现。欢迎各位感兴趣开发者阅读。

问题描述

有一个数组，现要找出数组中任意一个重复的元素。它的规则如下：

1. 给定一个长度为n的数组，数组中每个元素的取值范围为：0~n-1
2. 数组中某些数字是重复的，但是不知道哪些数字重复了，也不知道重复了几次
3. 求数组中任意一个重复的数字

实现思路

这个问题的实现思路有三种：

• 排序方法实现
• 哈希表辅助实现
• 动态排序法实现

接下来，我们来一一讲解下这三种实现思路。

排序方法实现

用排序方法实现分为两步：

1. 先用快速排序对数组进行排序
2. 遍历排序好的数组，如果其相邻的两个元素相等就代表数组中有重复的数字，将其返回即可。

接下来，我们通过一个例子来验证下上述思路。

声明一个数组：[8, 1, 2, 3, 4, 3, 3, 4, 5]

1. 用快速排序对上述数组进行排序，排序好的数组为: [1, 2, 3, 3, 3, 4, 4, 5, 8]
   
2. 遍历数组，判断i号位置的元素与i+1位置的元素是否相等。

1. i = 0时，i号位置的元素为1，i+1位置的元素是2，1 !== 2，继续下一轮遍历
2. i = 1时，i号位置的元素为2，i+1位置的元素是3，2 !== 3，继续下一轮遍历
3. i = 2时，i号位置的元素为3，i+1位置的元素是3，3 === 3，数组中有重复数字，存储i号位置的元素，退出循环。

3. 返回找到的重复数字
   

时间复杂度分析：调用快速排序其时间复杂度为O(nlog(n))，数组排序完成后只需遍历数组找到相邻的就退出，因此总的时间复杂度为O(nlog(n))

空间复杂度分析：空间复杂度分析：由于没有声明新的空间，因此空间复杂度为O(1)

使用排序方法我们可以解决这个问题，但是需要对数组进行排序，时间复杂度偏高。

哈希表辅助实现

我们可以额外声明一个哈希表，然后遍历数组，判断数组中的元素是否已存在于哈希表中，如果不存在就将其放入哈希表中，否则就代表数组中有重复元素，将其返回即可。

它的实现思路如下：

1. 声明一个空的哈希表
2. 从头到尾遍历数组，如果当前遍历到的元素不存在与哈希表中，就把它加入哈希表，否则就返回这个元素

接下来，我们通过一个例子来验证下上述思路。

声明一个数组：[8, 1, 2, 3, 4, 3, 3, 4, 5]

1. 声明一个哈希表: const hashMap = new HashMap()
   
2. 遍历数组，判断数组中的元素是否在哈希表中。

1. i = 0时，i号位置的元素为8，不在哈希表中，将其放入哈希表。
2. i = 1时，i号位置的元素为1，不在哈希表中，将其放入哈希表。
3. i = 2时，i号位置的元素为2，不在哈希表中，将其放入哈希表。
4. i = 3时，i号位置的元素为3，不在哈希表中，将其放入哈希表。
5. i = 4时，i号位置的元素为4，不在哈希表中，将其放入哈希表。
6. i = 5时，i号位置的元素为3，在哈希表中，存储i号位置的元素，终止循环。

3. 返回找到的重复数字
   

时间复杂度分析：遍历数组，判断哈希表中是否包含当前遍历到的元素时，都可以用O(1)的时间复杂度完成，所有元素遍历完就需要n个O(1)，因此总的时间复杂度为O(n)

空间复杂度分析：由于需要一个额外的哈希表来存储数据，情况最坏时数组的所有元素都会放进哈希表中，因此总的空间复杂度为：O(n)

使用哈希表辅助实现时，我们将时间复杂度降低了，但是代价是用了O(n)的空间存储哈希表，我们用空间换取了时间。

动态排序法实现

根据题意可知，数组中元素的取值范围在0~n-1，那么就可以得到如下结论：

• 如果数组中没有重复元素，那么第i号元素的值一定是当前下标(i)
• 如果数组中有重复元素，那么有些位置可能存在多个数字，有些位置可能没有数字

根据上述结论，我们可以得出下述实现思路:

1. 从头到尾遍历数组，存储第i号位置的元素，用m表示
2. 如果m的值等于当前下标(i)，则继续遍历。

• 否则就判断m的值是否等于数组下标为m处的值。
• 如果等于代表重复将其返回。
• 如果不等于，就交换数组i号位置的元素和m号位置的元素，更新m的值
• 继续判断m的值是否等于数组下标为m处的元素。

接下来，我们通过一个例子来验证下上述思路。

声明一个数组：[8, 1, 2, 3, 4, 3, 3, 4, 5]

• 从头到尾遍历数组，存储i号位置的元素，用m表示。

• 当下标为0时，m = 8。

• 此时，m的值为8，8 != 0，数组8号位置的元素为5，8 != 5，则交换array[0]和array[8]的位置，更新m的值。交换位置后的数组为：[5, 1, 2, 3, 4, 3, 3, 4, 8]
• 此时，m的值为5，5 != 0，数组5号位置的元素为3，3 != 5，则交换array[0]和array[5]的位置，更新m的值。交换位置后的数组为：[3, 1, 2, 3, 4, 5, 3, 4, 8]
• 此时，m的值为3，3!=0，数组3号位置的元素为3，3 === 3，元素重复，返回m。
• 问题解决，重复数字为3。

时间复杂度分析：每个数字最多只要交换2次就能找到它的位置，因此总的时间复杂度为O(n)

空间复杂度分析：所有操作都在原数组进行，没有用到额外的空间，所以空间复杂度为O(1)

使用动态排序法实现时，我们只是改变了数组的元素顺序，没有使用额外的空间，因此空间复杂度降低了，同时时间复杂度又保持在了O(n)。所以，这种解法相对与前面两种而言是最优的。

实现代码

接下来，我们来看看如何将其实现，此处我们使用TypeScript将其实现，我们先来看看如何设计这个类。

根据题意可知，并非所有数组都能使用上面的方法来求解。因此我们在设计类的时候，要判断调用者传入的参数是否满足题意。

• 新建一个ts文件，命名为：ArrayRepeatedNumber.ts
• 创建ArrayRepeatedNumber类，声明类内需要用到的辅助变量和构造函数。我们在构造函数中，对调用者传入的参数进行校验。

export class ArrayRepeatedNumber {
    private sort: Sort<number>;
    private readonly isTrue: boolean;
    constructor(private array: number[]) {
        this.isTrue = true;
        // 判断参数是否满足规则
        if (array == null || array.length <= 0) {
            this.isTrue = false;
            console.log("数组不能为空");
        }
        for (let i = 0; i < array.length; i++) {
            if (array[i] < 0 || array[i] > array.length - 1) {
                this.isTrue = false;
                console.log("数组中元素的取值范围为0～n-1");
            }
        }
        this.sort = new Sort(array);
    }
}

接下来，我们来看看上述三种实现思路的代码。

• 使用排序的方法解决

getRepeatedToSort(): number | void {
        if (this.isTrue) {
            // 排序数组
            const sortArray = this.sort.quickSort();
            // 重复的数字
            let val = -1;
            for (let i = 0; i < sortArray.length; i++) {
                // 排序完成后，相邻的两个数字相等就代表数组中有重复数字，将其返回
                if (sortArray[i] == sortArray[i + 1]) {
                    val = sortArray[i];
                    break;
                }
            }
            return val;
        }
    }

• 使用哈希表解决

getRepeatedToHashMap(): number | void {
        if (this.isTrue) {
            const hashMap = new HashMap();
            let val = -1;
            for (let i = 0; i < this.array.length; i++) {
                // 如果哈希表中存在当前元素就将其返回
                if (hashMap.get(this.array[i]) != null) {
                    val = this.array[i];
                    break;
                }
                // 不存在，将其加入哈希表
                hashMap.put(this.array[i], 0);
            }
            return val;
        }
    }

• 使用动态排序法解决

getRepeated(): number | void {
        if (this.isTrue) {
            for (let i = 0; i < this.array.length; i++) {
                // 存储数组i号位置的元素
                let m = this.array[i];
                // 判断m的值是否与当前下标一样，一样则继续下一轮循环
                while (m !== i) {
                    // 判断m的值是否等于数组m号位置的元素
                    if (m === this.array[m]) {
                        // 如果相等，代表重复，返回这个元素
                        return m;
                    }
                    // 交换数组的i号位置的元素和m号位置的元素
                    [this.array[i], this.array[m]] = [this.array[m], this.array[i]];
                    // 交换完毕，更新m的值
                    m = this.array[i];
                }
            }
            // 未找到
            return -1;
        }
    }

代码地址

完整代码，请移步：ArrayRepeatedNumber.ts

编写测试代码

我们用上面举的例子来验证下上述代码是否正确执行。

const arrayRepeatedNumber = new ArrayRepeatedNumber([8, 1, 2, 3, 4, 3, 3, 4, 5]);
const result = arrayRepeatedNumber.getRepeatedToSort();
if (result !== -1 && result != null) {
    console.log("Array Repeated Number to Sort: " + result);
}

const arrayRepeatedNumber = new ArrayRepeatedNumber([8, 1, 2, 3, 4, 3, 3, 4, 5]);
const result = arrayRepeatedNumber.getRepeatedToSort();
if (result !== -1 && result != null) {
    console.log("Array Repeated Number to HashMap: " + result);
}

const arrayRepeatedNumber = new ArrayRepeatedNumber([8, 1, 2, 3, 4, 3, 3, 4, 5]);
const result = arrayRepeatedNumber.getRepeated();
if (result !== -1 && result != null) {
    console.log("Array Repeated Number: " + result);
}

写在最后

• 公众号无法外链，文中链接可点下方阅读原文进行查看。