Voyz's Studio.

LeetCode算法笔记--寻找重复数

字数统计: 229阅读时长: 1 min
2021/01/07 Share

LeetCode算法笔记-Day60

287. Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one duplicate number in nums, return this duplicate number.

1.How can we prove that at least one duplicate number must exist in nums?
2.Can you solve the problem without modifying the array nums?
3.Can you solve the problem using only constant, O(1) extra space?
4.Can you solve the problem with runtime complexity less than O(n2)?

1
2
3
4
5
6
7
8
Example:

Input: nums = [1,3,4,2,2]
Output: 2

Input: nums = [3,1,3,4,2]
Output: 3

方法一:快慢指针

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function(nums) {
let slow = 0,
fast = 0;

while(true){
slow = nums[slow];
fast = nums[nums[fast]];
if(slow == fast) break;
}
slow = 0;
while(true){
slow = nums[slow];
fast = nums[fast];
if(slow == fast) return fast;
}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

方法二:JS Array POI

Answer:

1
2
3
4
5
6
7
8
9
/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function(nums) {
for(let i=0;i<nums.length;i++){
if(i != nums.lastIndexOf(nums[i])) return nums[i];
}
};
CATALOG
  1. 1. LeetCode算法笔记-Day60
    1. 1.1. 287. Find the Duplicate Number
    2. 1.2. 方法一:快慢指针
      1. 1.2.1. Answer:
    3. 1.3. 方法二:JS Array POI
      1. 1.3.1. Answer: