前言
前面一系列文章分享了数据结构与算法的基础知识,接下来分享一些算法题的解题思路与实现。欢迎各位感兴趣开发者阅读。
问题描述
有一个数组,现要找出数组中任意一个重复的元素。它的规则如下:
- 给定一个长度为n的数组,数组中每个元素的取值范围为:0~n-1
- 数组中某些数字是重复的,但是不知道哪些数字重复了,也不知道重复了几次
- 求数组中任意一个重复的数字
实现思路
这个问题的实现思路有三种:
- 排序方法实现
- 哈希表辅助实现
- 动态排序法实现
接下来,我们来一一讲解下这三种实现思路。
排序方法实现
用排序方法实现分为两步:
- 先用快速排序对数组进行排序
- 遍历排序好的数组,如果其相邻的两个元素相等就代表数组中有重复的数字,将其返回即可。
接下来,我们通过一个例子来验证下上述思路。
声明一个数组:[8, 1, 2, 3, 4, 3, 3, 4, 5]
- 用快速排序对上述数组进行排序,排序好的数组为:
[1, 2, 3, 3, 3, 4, 4, 5, 8]
- 遍历数组,判断i号位置的元素与i+1位置的元素是否相等。
- i = 0时,i号位置的元素为1,i+1位置的元素是2,
1 !== 2
,继续下一轮遍历 - i = 1时,i号位置的元素为2,i+1位置的元素是3,
2 !== 3
,继续下一轮遍历 - i = 2时,i号位置的元素为3,i+1位置的元素是3,
3 === 3
,数组中有重复数字,存储i号位置的元素,退出循环。
- i = 0时,i号位置的元素为1,i+1位置的元素是2,
- 返回找到的重复数字
时间复杂度分析:调用快速排序其时间复杂度为
O(nlog(n))
,数组排序完成后只需遍历数组找到相邻的就退出,因此总的时间复杂度为O(nlog(n))
空间复杂度分析:空间复杂度分析:由于没有声明新的空间,因此空间复杂度为
O(1)
使用排序方法我们可以解决这个问题,但是需要对数组进行排序,时间复杂度偏高。
哈希表辅助实现
我们可以额外声明一个哈希表,然后遍历数组,判断数组中的元素是否已存在于哈希表中,如果不存在就将其放入哈希表中,否则就代表数组中有重复元素,将其返回即可。
它的实现思路如下:
- 声明一个空的哈希表
- 从头到尾遍历数组,如果当前遍历到的元素不存在与哈希表中,就把它加入哈希表,否则就返回这个元素
接下来,我们通过一个例子来验证下上述思路。
声明一个数组:[8, 1, 2, 3, 4, 3, 3, 4, 5]
- 声明一个哈希表:
const hashMap = new HashMap()
- 遍历数组,判断数组中的元素是否在哈希表中。
- i = 0时,i号位置的元素为8,不在哈希表中,将其放入哈希表。
- i = 1时,i号位置的元素为1,不在哈希表中,将其放入哈希表。
- i = 2时,i号位置的元素为2,不在哈希表中,将其放入哈希表。
- i = 3时,i号位置的元素为3,不在哈希表中,将其放入哈希表。
- i = 4时,i号位置的元素为4,不在哈希表中,将其放入哈希表。
- i = 5时,i号位置的元素为3,在哈希表中,存储i号位置的元素,终止循环。
- 返回找到的重复数字
时间复杂度分析:遍历数组,判断哈希表中是否包含当前遍历到的元素时,都可以用
O(1)
的时间复杂度完成,所有元素遍历完就需要n个O(1),因此总的时间复杂度为O(n)
空间复杂度分析:由于需要一个额外的哈希表来存储数据,情况最坏时数组的所有元素都会放进哈希表中,因此总的空间复杂度为:
O(n)
使用哈希表辅助实现时,我们将时间复杂度降低了,但是代价是用了O(n)
的空间存储哈希表,我们用空间换取了时间。
动态排序法实现
根据题意可知,数组中元素的取值范围在0~n-1,那么就可以得到如下结论:
- 如果数组中没有重复元素,那么第i号元素的值一定是当前下标(i)
- 如果数组中有重复元素,那么有些位置可能存在多个数字,有些位置可能没有数字
根据上述结论,我们可以得出下述实现思路:
- 从头到尾遍历数组,存储第i号位置的元素,用m表示
- 如果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);
}
写在最后
- 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
- 本文首发于掘金,未经许可禁止转载💌
评论区