排序有关问题

剑指 Offer

剑指 Offer 45. 把数组排成最小的数

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

思路：
利用排序。

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (s1, s2) -> {
            return (s1 + s2).compareTo(s2 + s1);
        });
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s);
        }
        return sb.toString();
    }
}

剑指 Offer 51. 数组中的逆序对

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

思路：

class Solution {
    private int res = 0 ; //记录统计结果

    public int reversePairs(int [] nums) {
        Merge_Array(nums,0,nums.length-1);
        return res;
    }

    public void Merge_Array(int[] array,int origin,int end){
        if (origin>=end){ //只有一个值吗，不再进行归并
            return;
        }
        int mid = (origin + end) / 2 ;
        //左归并
        Merge_Array(array,origin,mid);
        //右归并
        Merge_Array(array,mid+1,end);
        // 排序统计
        Merge(array,origin,end,mid);
    }

    public void Merge(int[] array,int orgin,int end,int mid){
        int[] temp = new int[end-orgin+1] ; //辅助数组
        int i = 0 ; //temp数组添加新结果，向后移动
        int p1 = orgin ; // 左边数组的起点
        int p2 = mid+1 ; // 右边数组的起点

        // p1 , p2 比较哪个小把哪个放到temp
        while (p1<=mid && p2 <=end){
            if (array[p1]<=array[p2]){
                temp[i++] = array[p1++] ;
            }else {
                temp[i++] = array[p2++] ;
                this.res = this.res + mid - p1 + 1;
                /**
                 * 数组A【7，8，9，10，11，12】
                 * 数组B【1，2，3，4，5，6】
                 * 
                 * 如果A[pa] > B[pb]
                 * 就说明 mid-pa+1个逆序数对
                 */
            }
        }

        if (p1>mid){  //说明左边全部添加到temp中，继续添加右边
            while (p2<=end){
                temp[i++] = array[p2++] ;
            }
        }
        if (p2>end){ //说明右边全部添加到temp中，继续添加左边
            while (p1<=mid){
                temp[i++] = array[p1++] ;
            }
        }
        //在原数组中用有序的值覆盖掉原来无序的值
        for (int j=0;j<temp.length;j++){
            array[orgin+j] = temp[j] ;
        }
    }
}

LeetCode

912. 排序数组

147. 对链表进行插入排序

88. 合并两个有序数组

315. 计算右侧小于当前元素的个数

75. 颜色分类

215. 数组中的第K个最大元素

面试题

长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的交换，完成以下函数

public class Solution {
    /**
     * 交换数组里n和0的位置
     * @param array 数组
     * @param len 数组长度
     * @param n 和0交换的数
     */
    // 不要修改以下函数内容
    public void swapWithZero(int[] array, int len, int n) {
        Main.SwapWithZero(array, len, n);
    }
    // 不要修改以上函数内容


    /**
     * 通过调用swapWithZero方法来排序
     * @param array 存储有[0,n)的数组
     * @param len 数组长度
     */
    public void sort(int[] array, int len) {
        // 完成这个函数
        for (int i = 0; i < array.length; i++) {
            if(array[i] == i){
                continue;
            }
            //因只能与0交换，所以要先让0在array[i]这个位置上
            swapWithZero(array, len, array[i]);
            //然后将i与0交换，即可使数组array[i]==i
            swapWithZero(array, len, i);
        }
    }
}