剑指 Offer 03. 数组中重复的数字
文章目录

题目

题目的需求非常简单, 就是从数组里面找出相同的数字.

1
2
3
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3

限制:

1
2 <= n <= 100000

题解

这个问题主要考虑是对不同资源的取舍

  • 时间优先解法: 循环这个数组, 然后创建哈希表, 一旦发现字典里面存在这个数字就立刻返回.
  • 空间优先解法 1: 原地排序数组, 循环当前数组, 和后面一个元素比较是否相等.
  • 空间优先解法 2: 前后指针比较
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
/**
* @param {number[]} nums
* @return {number}
*/

// 时间优先解法: 循环这个数组, 然后创建哈希表, 一旦发现字典里面存在这个数字就立刻返回.

var findRepeatNumber = function(nums) {
let map = {}
for (let i = 0; i < nums.length; i++) {
const e = nums[i]
if (!map[e]) {
map[e] = true;
} else {
return e
}
}
};

// 空间优先解法: 原地排序数组, 循环当前数组, 和后面一个元素比较是否相等.
// 也可以通过指针进行比较
var findRepeatNumber = function(nums) {
nums.sort()
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] === nums[i + 1]) return nums[i]
}
};

// 鸽巢原理,因为出现的元素值 < nums.size(); 所以我们可以将见到的元素 放到索引的位置,如果交换时,发现索引处已存在该元素,则重复 O(N) 空间O(1)
var findRepeatNumber = function(nums) {
let i = 0;
while (i < nums.length) {
if (nums[i] === i) {
i++
} else {
const num = nums[i];
if (nums[num] === num) return num
const tmp = nums[num];
nums[num] = num
nums[i] = tmp
}
}
};