剑指offer Search

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

Posted by franki on April 17, 2021

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

思路

  1. 遍历数组
  2. 每次对比当前下标与当前值是否相等，相等就继续下一个；若不等，继续比较当前值与以当前值作为下标对应的值，若相等，则说明有重复，若不等，就交换两者的位置；这个过程其实就是重排，把数字放到应该在的位置上

代码

function duplicate(num) {
    var arr = [];
    if (num.length === 0 || !num) {
        return false;
    }
    for (let i=0; i<num.length; i++) {
        while (num[i] !== i) {
            if (num[i] === num[num[i]]) {
                arr.push(num[i]);
                break;
            }
            swap(num, i, num[i]);
        }
    }
    return arr;
}
function swap(num, i, j) {
    [num[i], num[j]] = [num[j], num[i]];
}

复杂度分析

  • 时间复杂度: O(MN)
  • 空间复杂度: O(N)
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
    FRIENDS