排序

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

myself题解思路：双指针的思想：左右寻找偶数和奇数然后进行交换，特殊的一点在于有可能数组是全奇或者全偶，所以需要在while循环中加入x< y的判定。

class Solution {
    public int[] exchange(int[] nums) {
        int x = 0;
        int y = nums.length - 1;
        while (x < y) {
            while (x < y && nums[x] % 2 != 0) {
                x++;
            }
            while (x < y && nums[y] % 2 == 0) {
                y--;
            }
            if (x < y) {
                swap(x, y, nums);
            }
        }
        return nums;
    }
    public void swap(int x, int y, int[] nums) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}

总结：首尾双指针 定义头指针 left ，尾指针 right . left 一直往右移，直到它指向的值为偶数 right 一直往左移， 直到它指向的值为奇数 交换 nums[left] 和 nums[right]. 重复上述操作，直到 left == right .

注意：if（x<y）这一步判断条件

题解思路：快慢双指针

• 定义快慢双指针fast和low，fast在前，low在后。
• fast的作用是向前搜索奇数位置，low的作用是指向下一奇数应当存放的位置
• fast向前移动，将它搜索到奇数时，将它和nums[low]交换，此时low向前移动一个位置。

• 重复上述操作，直到fast指向数组末尾。

  class Solution {
    public int[] exchange(int[] nums) {
        int slow = 0;
        int fast = 0;
        while (fast < nums.length) {
            if (nums[fast] % 2 != 0) {        //(nums[fast] & 1) != 0
                swap(slow, fast, nums);
                slow++;
            }
            fast++;
        }
        return nums;
    }
  
    public void swap(int x, int y, int[] nums) {
        int tem = nums[x];
        nums[x] = nums[y];
        nums[y] = tem;
    }
  }
  

  总结：可以通过nums[fast] % 2 != 0判断奇数还是偶数

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

解题思路：

• 此题求拼接的“最小数字”，本质上是一个排序问题。。
• 排序判断规则：设nums任意两个数字的字符串格式x和y，则
  • 若拼接的字符串x+y>y+x，则m>n;
  • 反之，若x+y<y+x，则n<m；

• 根据以上规则，套用任何排序方法对nums执行排序即可。

  class Solution {
    public String minNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        int n = nums.length;
        String[] tem = new String[n];
        for (int i = 0; i < n; i++)
            tem[i] = nums[i] + "";
        Arrays.sort(tem, (s1,s2) -> (s1+s2).compareTo(s2 + s1));
        StringBuilder res = new StringBuilder();
        for (String s : tem) {
            res.append(s);
        }
        return res.toString();
    }
  

  总结：Arrays.sort(tem,(s1,s2)->(s1+s2).compareTo(s2+s1))，匿名表达式。

• 题解方法2：快排思想

  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]);
        fastSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
    void fastSort(String[] strs, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        String tmp = strs[i];
        while(i < j) {
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        fastSort(strs, l, i - 1);
        fastSort(strs, i + 1, r);
    }
  }
  

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

解题思路：

直观来看，使用暴力统计法即可，即遍历数组的所有数字对并统计逆序对数量，此方法时间复杂度为O(N2)，观察题目给定的数字长度范围0<N<50000,可知此复杂度是不能接受的。

[归并排序」与「逆序对」是息息相关的。归并排序体现了 “分而治之” 的算法思想，具体为：

• 分： 不断将数组从中点位置划分开（即二分法），将整个数组的排序问题转化为子数组的排序问题；
• 治： 划分到子数组长度为 1 时，开始向上合并，不断将较短排序数组合并为较长排序数组，直至合并至原数组时完成排序；

  如下图所示，为数组[7,3,2,6,0,1,5,4]的归并排序过程

算法流程

merge_sort()归并排序与逆序对统计：
1、终止条件：当l>=r是，代表子数组长度为1，此时终止划分；
2、递归划分：计算数组中点m，递归划分左子数组merge_sort（l,m）和右子数组merge_sort（m+1，l）；
3、合并与逆序对统计：
1、暂存数组nums闭区间【i，r】内的元素至辅助数组tmp；
2、循环合并： 设置双指针 ii , jj 分别指向左 / 右子数组的首元素；
当 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 ；
4、返回值： 返回直至目前的逆序对总数 res ；

reversePairs() 主函数：
1、初始化：辅助数组tmp，用于合并阶段暂存元素；
2、返回值：执行归并排序merge_sort( ),并返回逆序对总数即可。

在标准归并排序模板上进行操作

class Solution {
    int count;
    public int reversePairs(int[] nums) {
        int left=0,right=nums.length-1;
        merge(nums,left,right);
        return count;
    }

    public void merge(int[] nums,int left,int right){
        if(left>=right)
            return;
        int mid=(right+left)/2;
        merge(nums,left,mid);
        merge(nums,mid+1,right);
        mergeSort(nums,left,mid,right);
    }

    public void mergeSort(int[] nums,int left,int mid,int right){
        int[] temparr=new int[right-left+1];
        int index=0;
        int temp1=left,temp2=mid+1;

        while(temp1<=mid&&temp2<=right){
            if(nums[temp1]<=nums[temp2])
                temparr[index++]=nums[temp1++];
            else{
                count+=(mid-temp1+1);
                temparr[index++]=nums[temp2++];
            }
        }

        while(temp1<=mid){
            temparr[index++]=nums[temp1++];
        }

        while(temp2<=right)
            temparr[index++]=nums[temp2++];

        for(int i=0;i<temparr.length;i++){
            nums[i+left]=temparr[i];
        }
    }
}