剑指offer Binary Search

剑指offer-不修改数组找出重复的数字

Posted by franki on April 17, 2021

寻找重复数字 0~N-1 个数字

长度为n+1，所有的数字在1~n的范围内，所以至少有一个数字是重复的。请找出任意一个重复的数字，但不能修改输入的数字。例如[2,3,5,4,3,2,6,7]那么对应的输出应该是数字2后者3

思路

  1. 方法一使用一个n+1的数组，直接把原数组里面的每一个值放到对一个的数组下标里这样很容易知道哪个值是重复的
  2. 方法二 二分法

代码

方法一 代码

function isRepy(nums) {
    const copyNums = [];
    for (let i=0; i<nums.length; i++) {
        if (copyNums[nums[i]]) {
            return nums[i];
        }
        copyNums[nums[i]] = true;
    }
    return -1;
}

方法二 代码

function getDuplication(nums, len) {
    if (!nums || len <= 0) {
        return -1;
    }

    let start = 1;
    let end = len - 1;

    while (end >= start) {
        let middle = ((end - start) >> 1) + start;
        let count = countRange(nums, len, start, middle);
        if (end === start) {
            if (count > 1) {
                return start;
            }
            break;
        }
        if (count > (middle - start + 1)) {
            end = middle;
        } else {
            start = middle + 1;
        }
    }
    return -1;
}

function countRange(nums, len, start, end) {
    if (!nums) {
        return 0;
    }
    let count = 0;
    for (let i=0; i<len; i++) {
        if (nums[i] >= start && nums[i] <= end) {
            count++;
        }
    }
    return count;
}

复杂度分析

方法一

  • 时间复杂度: O(N)
  • 空间复杂度: O(N)

方法二

  • 时间复杂度: O(NlogN)
  • 空间复杂度: O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG 科学上网 工具
    FRIENDS