Voyz's Studio.

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

算法题 热题HOT100 快慢指针
字数统计: 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：
Total : 137
2021
2020
2019
2018
技术贴 JavaScript Flutter 算法题 热题HOT100 哈希表 滑动窗口 回溯算法 链表 二分法 矩阵 动态规划 贪心算法 指针 快速排序 迭代 二叉树 数组 快慢指针 排序 背包问题 单调栈 栈 DFS 岛屿问题 React Native React 旅行记 效率工具 python 小程序 英语 生活 足球 算法 性能优化 ES6 TypeScript koa