leetcode QuickSort

leetcode 179题

Posted by franki on September 1, 2021

leetcode 179题 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

示例 3：

输入：nums = [1]
输出："1"

示例 4：

输入：nums = [10]
输出："10"

思路

快速排序

代码

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
    // 利用快速排序，根据字符的大小来排序
    if (nums.length === 0) {
        return "";
    }
    const numStrs = nums.map(item => item+'');
    partitionStringSort(numStrs, 0, numStrs.length - 1);
    let res = "";
    for (let i=0; i<numStrs.length; i++) {
        const str = numStrs[i];
        if (res === '0') {
            continue;
        }
        res += str;
    }
    return res;
};

function partition(a, lo, hi) {
    const pivot = a[hi];
    let i = lo-1;
    for (let j=lo; j<hi; j++) {
        const ajStr = a[j] + pivot;
        const pivotStr = pivot + a[j];
        if (ajStr > pivotStr) {
            i++;
            [a[i], a[j]] = [a[j], a[i]];
        }
    }
    [a[i+1], a[hi]] = [a[hi], a[i+1]];
    return i+1;
}

function partitionStringSort(a, lo, hi) {
    if (lo >= hi) {
        return;
    }
    const p = partition(a, lo, hi);
    partitionStringSort(a, lo, p-1);
    partitionStringSort(a, p+1, hi);
}

复杂度分析

  • 时间复杂度：O(N^2)
  • 空间复杂度：O(N^2)
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