前面一系列文章分享了数据结构与算法的基础知识,接下来分享一些算法题的解题思路与实现。欢迎各位感兴趣开发者阅读。
有一个数组,现要找出数组中任意一个重复的元素。它的规则如下:
这个问题的实现思路有三种:
接下来,我们来一一讲解下这三种实现思路。
用排序方法实现分为两步:
接下来,我们通过一个例子来验证下上述思路。
声明一个数组:[8, 1, 2, 3, 4, 3, 3, 4, 5]
[1, 2, 3, 3, 3, 4, 4, 5, 8]
1 !== 2
,继续下一轮遍历2 !== 3
,继续下一轮遍历3 === 3
,数组中有重复数字,存储i号位置的元素,退出循环。时间复杂度分析:调用快速排序其时间复杂度为
O(nlog(n))
,数组排序完成后只需遍历数组找到相邻的就退出,因此总的时间复杂度为O(nlog(n))
空间复杂度分析:空间复杂度分析:由于没有声明新的空间,因此空间复杂度为
O(1)
使用排序方法我们可以解决这个问题,但是需要对数组进行排序,时间复杂度偏高。
我们可以额外声明一个哈希表,然后遍历数组,判断数组中的元素是否已存在于哈希表中,如果不存在就将其放入哈希表中,否则就代表数组中有重复元素,将其返回即可。 它的实现思路如下:
接下来,我们通过一个例子来验证下上述思路。
声明一个数组:[8, 1, 2, 3, 4, 3, 3, 4, 5]
const hashMap = new HashMap()
时间复杂度分析:遍历数组,判断哈希表中是否包含当前遍历到的元素时,都可以用
O(1)
的时间复杂度完成,所有元素遍历完就需要n个O(1),因此总的时间复杂度为O(n)
空间复杂度分析:由于需要一个额外的哈希表来存储数据,情况最坏时数组的所有元素都会放进哈希表中,因此总的空间复杂度为:
O(n)
使用哈希表辅助实现时,我们将时间复杂度降低了,但是代价是用了O(n)
的空间存储哈希表,我们用空间换取了时间。
根据题意可知,数组中元素的取值范围在0~n-1,那么就可以得到如下结论:
根据上述结论,我们可以得出下述实现思路:
接下来,我们通过一个例子来验证下上述思路。
声明一个数组:[8, 1, 2, 3, 4, 3, 3, 4, 5]
8 != 0
,数组8号位置的元素为5,8 != 5
,则交换array[0]
和array[8]
的位置,更新m的值。交换位置后的数组为:[5, 1, 2, 3, 4, 3, 3, 4, 8]
5 != 0
,数组5号位置的元素为3,3 != 5
,则交换array[0]
和array[5]
的位置,更新m的值。交换位置后的数组为:[3, 1, 2, 3, 4, 5, 3, 4, 8]
3!=0
,数组3号位置的元素为3,3 === 3
,元素重复,返回m。时间复杂度分析:每个数字最多只要交换2次就能找到它的位置,因此总的时间复杂度为O(n)
空间复杂度分析:所有操作都在原数组进行,没有用到额外的空间,所以空间复杂度为O(1)
使用动态排序法实现时,我们只是改变了数组的元素顺序,没有使用额外的空间,因此空间复杂度降低了,同时时间复杂度又保持在了O(n)
。所以,这种解法相对与前面两种而言是最优的。
接下来,我们来看看如何将其实现,此处我们使用TypeScript将其实现,我们先来看看如何设计这个类。 根据题意可知,并非所有数组都能使用上面的方法来求解。因此我们在设计类的时候,要判断调用者传入的参数是否满足题意。
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);
}