主题
03. 数组中重复的数字
来源
https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
题目
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
限制:
2 <= n <= 100000
思路
如果时间复杂度优先,可以使用 javascript 的 object 对象作为 hashMap,创建一个 map,循环数组,把元素存储到 map 里,如果已经存在,则返回该元素。
时间复杂度 O(1),空间复杂度 O(n)。
解题
js
/**
* @param {number[]} nums
* @return {number}
*/
const findRepeatNumber = function (nums) {
const map = {};
for (const num of nums) {
if (num in map) return num;
map[num] = 1;
}
};
思路 2
如果空间复杂度优先,使用二分法降低时间复杂度,题目前提是“在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内”,可以求出中间值,判断小于等于中间值的元素数量是否大于中间值,如果大于,重复的数字就在小于等于中间值的这边,反之在另一边,再利用二分法进行查找。
时间复杂度 O(nlogn),空间复杂度 O(1)。
解题 2
js
/**
* @param {number[]} nums
* @return {number}
*/
const findRepeatNumber = function (nums) {
const len = nums.length;
let start = 0;
let end = len - 1;
while (start < end) {
const mid = start + ((end - start) >> 1);
let counter = 0;
for (const num of nums) {
if (num >= start && num <= mid) {
counter++;
}
}
if (counter > mid) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
};
// >>1 位运算右移一位,等同于除2并向下取整
从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch