leetcode QuickSort

leetcode 164题

Posted by franki on August 25, 2021

leetcode 164题 最大间距

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例 1：

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2：

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

思路

快速排序 + 遍历

代码

function maximumGap(nums) {
    // 先排序，后遍历查找最大的间隔
    if (nums.length < 2) {
        return 0;
    }
    quickSort(nums, 0, nums.length - 1);
    let res = 0;
    for (let i=0; i<nums.length-1; i++) {
        if ((nums[i+1] - nums[i]) > res) {
            res = nums[i+1] - nums[i];
        }
    }
    return res;
}

function partition(nums, low, high) {
    const pivot = nums[high]
    let i = low-1;
    for (let j = low; j<high; j++) {
        if (nums[j] < pivot) {
            i++;
            [nums[j], nums[i]] = [nums[i], nums[j]];
        }
    }
    [nums[i+1], nums[high]] = [nums[high], nums[i+1]];
    return i+1;
}

function quickSort(nums, low, high) {
    if (low >= high) {
        return;
    }
    const p = partition(nums, low, high);
    partition(nums, low, p-1);
    partition(nums, p+1, high);
}

复杂度分析

  • 时间复杂度：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