跳到主要内容

元素组合

把数组排成最小的数​

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例1:

输入: [10,2]
输出: "102"

示例2:

输入: [3,30,34,5,9]
输出: "3033459"

方案A 快速排序​

思路: 排序判断规则为

  • 若拼接字符串 x + y > y + x ，则 x “大于” y ；
  • 反之，若 x + y < y + x ，则 x “小于” y ；

x “小于” y 代表：排序完成后，数组中 x 应在 y 左边；“大于” 则反之。

根据以上规则，套用快速排序方法对 numsn 执行排序即可。

:::details 点击查看代码

function minNumber(nums) {
    const sort=(nums,start,end)=>{
        if(start>=end){
            return 
        }
        let left=start;
        let right=end;
        let pivot=nums[Math.floor((left+right)/2)];
        while(left<=right){
            while(Number(String(nums[left])+String(pivot))<Number((String(pivot)+String(nums[left])))){
                left++;
            }
            while(Number(String(nums[right])+String(pivot))>Number((String(pivot)+String(nums[right])))){
                right--;
            }
            if(left<=right){
                [nums[left],nums[right]]=[nums[right],nums[left]];
                left++;
                right--;
            }
        }
        sort(nums,start,right);
        sort(nums,left,end);
    }
    sort(nums,0,nums.length-1);
    return nums.reduce((prev,curr)=>prev+curr,'')
};

:::

性能分析:

  • 时间复杂度:O(NlogN)

  • 空间复杂度:O(N)

数组中的逆序对​

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例1:

输入: [7,5,6,4]
输出: 5

方案A 归并思想​

思路: 归并排序的合并阶段 本质上是合并两个排序数组的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。

  • 终止条件： 当 l≥r 时，代表子数组长度为 1 ，此时终止划分；
  • 递归划分： 计算数组中点 m ，递归划分左子数组 merge_sort(l, m) 和右子数组 merge_sort(m + 1, r) ；
  • 合并与逆序对统计：
    • 暂存数组 nums 闭区间 [i,r] 内的元素至辅助数组 tmp ；
    • 循环合并： 设置双指针 i , j 分别指向左 / 右子数组的首元素；
    • 当 i = m + 1 时： 代表左子数组已合并完，因此添加右子数组当前元素 tmp[j] ，并执行 j = j + 1 ；
    • 否则，当 j = r + 1 时： 代表右子数组已合并完，因此添加左子数组当前元素 tmp[i] ，并执行 i = i + 1；
    • 否则，当 tmp[i]≤tmp[j] 时： 添加左子数组当前元素 tmp[i] ，并执行 i = i + 1；
    • 否则（即 tmp[i] > tmp[j]）时： 添加右子数组当前元素 tmp[j] ，并执行 j = j + 1 ；此时构成 m - i + 1 个「逆序对」，统计添加至 res ；

:::details 点击查看代码

function mergeAndCount(nums,start,middle,end){
    let count=0;
    let left=start;
    let right=middle+1;
    let temp=[];
    let t=0;
    while(left<=middle&&right<=end){
        if(nums[left]<=nums[right]){
            temp[t++]=nums[left++];
        }else{
            temp[t++]=nums[right++];
            count+=middle-left+1;
        }
    }
    while(left<=middle){
        temp[t++]=nums[left++];
    }
    while(right<=end){
        temp[t++]=nums[right++];
    }
    for(let i=0;i<t;i++){
        nums[start++]=temp[i];
    }
    return count;
}
function mergeSortAndCount(nums,start,end){
    if(start>=end){
        return 0;
    }
    let middle=Math.floor((start+end)/2);
    let leftCount=mergeSortAndCount(nums,start,middle);
    let rightCount=mergeSortAndCount(nums,middle+1,end);
    let crossCount=mergeAndCount(nums,start,middle,end);
    return leftCount+crossCount+rightCount;
}
function reversePairs(nums) {
    if(nums.length==0){
        return 0
    }
    return mergeSortAndCount(nums,0,nums.length-1);
};

:::

性能分析:

  • 时间复杂度：O(nlogn)。
  • 空间复杂度：O(n)，

颜色分类​

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例1:

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例2:

输入：nums = [2,0,1]
输出：[0,1,2]

示例3:

输入：nums = [0]
输出：[0]

方案A 三路快速排序​

思路: 将红色0放在最左边； 将蓝色2放在最右边；剩下的就是白色1

  • 设置三个 red, blue, i 指针;定义：nums[0...red] == 0，nums[red+1...i-1] = 1，nums[blue...n-1] == 2，遍历一遍改数列保持这个定义。

:::details 点击查看代码

function sortColors(nums){
    let red=-1;
    let blue=nums.length;
    let i=0;
    while(i<blue){
        if(nums[i]==0){
            red++;
            [nums[red],nums[i]]=[nums[i],nums[red]];
            i++;
        }else if(nums[i]==2){
            blue--;
            [nums[blue],nums[i]]=[nums[i],nums[blue]];
        }else{
            i++
        }
    }
}

:::