LeetCode上的排序题

排序

选择排序：

  1. for (int i = n - 1; i >= 0; i--)
  2. {
  3.     int idx = 0;
  4.     for (int j = 0; j <= i; j ++)
  5.     {
  6.         if (n[j] > n[idx])
  7.             idx = j;
  8.     }
  9.     swap(n[idx], n[i]);
  10. }

插入排序

  1. import java.io.*;
  2. import java.util.Scanner;
  3. class Main{
  4.     static int n;
  5.     public static void main(String[] args){
  6.         Scanner scan = new Scanner(System.in);
  7.         n = scan.nextInt();
  8.         int []sort = new int[n];
  9.         for (int i = 0; i < n; i++) 
  10.             sort[i] = scan.nextInt();
  11.         for (int i = 1; i < n; i ++){
  12.             for (int j = i - 1; j >= 0 && sort[j] > sort[j + 1]; j--){
  13.                 int t = sort[j]; sort[j] = sort[j + 1]; sort[j + 1] = t;
  14.             }
  15.         }
  16.         for (int i = 0; i < n; i ++)
  17.             System.out.print(sort[i] + " ");
  18.         return;
  19.     }
  20. }

快速排序：

关键点在于搞清楚一点：遍历完i, j指针作为临界点的意义 。
ij指针移动完后：

  1. 1. j == i or j = i - 1
  2. 2. q[l, i - 1]<=基准值， q[i， r]>=x 
  3. 4. q[j + 1, r]>= x ; q[l, j] <= x

所以递归区间是 [l, i - 1](<=x) or [i , r](>=x) 基准为q[l]
[l, j](<=x)or [j + 1, r](>=x)
具体选择哪种情况，要看基准值x

当x == q[l]或者q[l + r >> 1], 选择区间[l, j] and [j + 1,r](因为以q[l]/q[l + r >> 1]为基准的时候，即使数组是递增的，j也不会最终停在r的位置。j停在右边的条件是j—只执行了一次，但x为基准，i指针会卡一次，j无论会不会卡都会至少执行两次)
当x == q[r]或者q[l + r + 1 >> 1], 选择区间[l, i - 1] and [i, r](同理)

  2.  public static void quickSort(int l, int r, int[] q){
  3.         if (l >= r) return;
  4.         int i = l - 1, j = r + 1;
  5.         int x = q[r];
  6.         while (i < j){
  7.             do i ++; while(q[i] < x);
  8.             do j --; while(q[j] > x);
  9.             if (i < j) {
  10.                 int t = q[i];
  11.                 q[i] = q[j];
  12.                 q[j]  = t;
  13.             }
  14.         }
  15.         quickSort(l, i - 1, q);
  16.         quickSort(i, r, q);
  17.     }

模板题

类似快排思想32. 调整数组顺序使奇数位于偶数前面 

  1. class Solution {
  2.     public int[] exchange(int [] array) {
  3.         // 快排，双指针
  4.         for (int i = 0, j = array.length - 1; i < j; ){
  5.             while (i < array.length && array[i] % 2 != 0) i++;
  6.             while (j >= 0 && array[j] % 2 == 0) j--;
  7.             if (i < j){
  8.                 int tmp = array[i];
  9.                 array[i] = array[j];
  10.                 array[j] = tmp;
  11.             }
  12.         }
  13.         return array;
  14.     }
  15. }

按照字典序排序 242. 有效的字母异位词

這道題手寫快排。 把String轉成StringBuilder做的。。轉成char[]好做一些（可以使用Arrays.sort）。

  1. class Solution {
  2.     public boolean isAnagram(String s, String t) {
  3.         //把两个字符串快排 如果equals是一样的
  4.         int n1 = s.length(), n2 = t.length();
  5.         //轉換成StringBuilder，有replace函數，可以更換字符串
  6.         StringBuilder sb = new StringBuilder(s);
  7.         StringBuilder tb = new StringBuilder(t);
  8.         //轉成String
  9.         t = quickSort(0, n2 - 1, tb).toString();
  10.         s = quickSort(0, n1 - 1, sb).toString();
  12.         for(int i = 0; i < n1; i ++)
  13.             System.out.print(s.charAt(i));
  14.          System.out.println();
  15.         for(int i = 0; i < n2; i ++)
  16.             System.out.print(t.charAt(i));
  17.         if (s.equals(t)){
  18.             return true;
  19.         }
  20.         return false;
  21.     }
  23.     public StringBuilder quickSort(int l, int r, StringBuilder sb){
  24.         if (l >= r) return sb;
  25.         int i = l - 1, j = r + 1;
  26.         int mid = (i + j) / 2;
  27.         while(i < j){
  28.             do i ++; while(Integer.valueOf(sb.charAt(i)).intValue() < Integer.valueOf(sb.charAt(mid)).intValue());
  29.             do j --; while(Integer.valueOf(sb.charAt(j)).intValue() > Integer.valueOf(sb.charAt(mid)).intValue());
  30.             if (i < j){
  31.                 String t = new String();
  32.                 t = sb.substring(j, j + 1);
  33.                 sb.replace(j, j + 1, sb.substring(i, i + 1));
  34.                 sb.replace(i, i + 1, t);
  35.             }
  36.         }
  37.         sb = quickSort(l, j,sb);
  38.         sb = quickSort(j + 1, r, sb); 
  39.         return sb;
  40.     }
  41. }

或者使用hashMap

  1. class Solution {
  2.     public boolean isAnagram(String s, String t) {
  3.         //使用hashMap,記錄每個字符和出現次數
  4.         char[] charS = s.toCharArray();
  5.         char[] charT = t.toCharArray();
  6.         HashMap<Character, Integer> hash1 = new HashMap<>();
  7.         HashMap<Character, Integer> hash2 = new HashMap<>();
  8.         for (int i = 0; i < charS.length; i ++)
  9.             hash1.put(charS[i], hash1.getOrDefault(charS[i], 0) + 1);
  10.         for (int i = 0; i < charT.length; i ++)
  11.             hash2.put(charT[i], hash2.getOrDefault(charT[i], 0) + 1); 
  12.         return hash1.equals(hash2);
  13.     }
  14. }`

快速选择

排序 - 图1#card=math&code=o%28n%29)

快速选择就是求第k大/小的数

利用快排的原理，在每次递归的时候求出 i 在[l, i - 1]就是>=mid的数。因此，如果k <= i 就只需要递归左区间，k > i 就递归有区间， k == i 就返回。

说明第j个最大的数是mid，如果k >= j，因此只要递归[l, j]就可以

第i - 1大的数是mid， 当k < i,说明递归[l, i - 1]

  1. if (k < j) return sort(l, j, k, nums);
  2.         else if (k > j) return sort(j + 1, r, k , nums); 
  3.         else return nums[j];

不行吗？

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

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int l = 0, r = n - 1;
        return sort(l, r, k - 1, nums);
    }
    public int sort(int l, int r, int k, int[] nums){
        if (l >= r) return nums[k];
        int i = l - 1, j = r + 1, mid = nums[l + r >> 1];
        while (i < j){
            do i ++; while(nums[i] > mid);
            do j --; while(nums[j] < mid);
            if (i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        //System.out.println(nums[i] + " " + nums[j] + " " + nums[mid]);
        if (k < i) return sort(l, j, k, nums);
        else return sort(j + 1, r, k , nums); 
    }
}

或者

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int l = 0, r = n - 1;
        return sort(l, r, k - 1, nums);
    }
    public int sort(int l, int r, int k, int[] nums){
        if (l >= r) return nums[k];
        int i = l - 1, j = r + 1, mid = nums[l + r + 1>> 1];
        while (i < j){
            do i ++; while(nums[i] > mid);
            do j --; while(nums[j] < mid);
            if (i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        if (k < i) return sort(l, i - 1, k, nums);
        else return sort(i, r, k , nums); 
    }
}

归并排序

时间复杂度 O(logn)

空间复杂度 迭代 o(1) 递归 o(logn)

归并排序 递归
public static void mergeSort(int l, int r, int[] q, int[] t){
        if (l >= r) return;
        int k = 0;
        int i = l, mid = (l + r) / 2, j = mid + 1;
        mergeSort(l, mid, q, t);
        mergeSort(j, r, q, t);
        while(i <= mid && j <= r){
            if (q[i] <= q[j])t[k ++] = q[i ++];
            else t[k ++] = q[j ++];
        }
        while(i <= mid)t[k ++] = q[i++];
        while(j <= r) t[k ++] = q[j ++];

        for (i = l, j = 0; i <= r; i ++)
        {
            q[i] = t[j ++];
        }
    }

归并需要从小区间到大区间排序，因为他要求前后两个区间中的每个区间是**有序**的


迭代算法

148. 排序链表

### 解题思路

由于链表不适合使用递归，使用迭代法求归并排序

时间复杂度o(2nlogn >=nlogn) 空间复杂度o(1)在循环内开辟的节点，每次跳出第二层循环 之前的dummy都会被GC，因此只用了一个节点的空间

排序 - 图2

### 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        //存到数组里面，排完序再更新到链表里面 时间复杂度o(n + nlog), space o(N)
        //如果需要o(N)的空间，使用迭代的归并排序
        int n = 0;
        ListNode e = head;
        while (e != null) {e = e.next; n ++;}

        for (int i = 1; i < n; i *= 2){
            ListNode dummy = new ListNode(-1);
            ListNode cur = dummy;
            ListNode p = head, q, o = head;
            for (int j = 1; j <= n; j += i * 2){
                q = p = o;
                for (int k = 1;k <= i && q != null; k ++) q = q.next;
                int l = 0, r = 0;
                while (l < i && r < i && q != null && p != null){
                    if (p.val <= q.val) {
                        cur.next = p;
                        cur = cur.next;
                        p = p.next;l++;
                    }
                    else {
                        cur = cur.next = q; q = q.next;r++;
                    }
                } 
                while (l < i && p != null){cur = cur.next = p; p = p.next; l++;}
                while (r < i && q != null){cur = cur.next = q; q = q.next; r++;}
                o = q;
                cur.next = null;
            }
            head = dummy.next;
            for (ListNode c = head; c != null; c = c.next)
                System.out.print(c.val);
            System.out.println();
        }
        return head;
    }
}

迭代归并LeetCode21. 合并两个有序链表

解题思路

类似于归并排序（不需要分治）的思路解法。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //合并有序的两个链表 ，类似于归并排序的思路
        ListNode cur1 = l1, cur2 = l2;
        ListNode head = new ListNode();
        ListNode res = head;
        while(cur1 != null && cur2 != null){
            if (cur1.val <= cur2.val) {
                res.next = new ListNode(cur1.val);
                res = res.next;
                cur1 = cur1.next;
            }
            else{
                res.next = new ListNode(cur2.val);
                res = res.next;
                cur2 = cur2.next;
            }
        }
        while(cur1 != null){
            res.next = new ListNode(cur1.val);
            res = res.next;
            cur1 = cur1.next;
        }
        while(cur2 != null){
            res.next = new ListNode(cur2.val);
            res = res.next;
            cur2 = cur2.next;
        }
        return head.next;
    }
}

归并过程中统计逆序对 65. 数组中的逆序对 - AcWing题库

class Solution {
    int res=  0;
    public int inversePairs(int[] nums) {
        //归并排序
        /*
            每次排序的时候判断，如果存在逆序的情况（nums[i] > nums[j]），说明[i, j) 和 j之间的都是逆序对
        */
        int l = 0, r = nums.length - 1;
        merge(l, r, nums);
        return res;
    }
    public void merge(int l, int r, int[] nums){
        if (l >= r) return;
        int mid = l + r >> 1;
        merge(l, mid, nums); merge(mid + 1, r, nums);
        int i = l, j = mid + 1;
        int[] tmp = new int[nums.length]; int k = 0;
        while (i <= mid && j <= r){
            if (nums[i] > nums[j]) {res += mid - i + 1; tmp[k++] = nums[j++];}
            else tmp[k++] = nums[i++];
        }
        while (i <= mid) {tmp[k++] = nums[i++]; };
        while (j <= r) tmp[k++] = nums[j++];
        for (i = l, j = 0; i <= r; i ++) nums[i] = tmp[j++];
        //System.out.println(res);
    }
}

堆排序

如何手写一个堆？堆就是一个完全二叉树。

完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

排序 - 图3

  1. 向堆中插入一个数 heap[++size] = x; up(size);
  2. 求集合中的最小值 heap[1]
  3. 删除最小值 heap[1] = heap[size]; size--; down(1);
  4. 删除任意一个数x heap[k] = heap[size]; size--; down(k); up(k);
  5. 修改任意一个元素 heap[k] = x; up(k); down(k);

其中重要的一点：

排序 - 图4

堆排序

import java.io.*;
import java.util.Scanner;

public class Main{
    static int n, m;
    static int[] heap = new int[100010];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String[] t = scan.nextLine().split(" ");
        n = Integer.parseInt(t[0]); m = Integer.parseInt(t[1]);
        for (int i = 1; i <= n; i++){
            heap[i] = scan.nextInt();
        }
        //从n/2开始down，z
        for (int i = n / 2; i != 0; i --){
            down(i);
        }
        while (m-- != 0){
            System.out.print(heap[1] + " ");
            heap[1] = heap[n--];
            down(1);
        }
    }
    //维护一个堆
    public static void down(int idx){
        int tmp = idx;
        if (idx * 2 <= n && heap[idx * 2] < heap[tmp]) tmp = idx * 2;
        if (idx * 2 + 1 <= n && heap[idx * 2 + 1] < heap[tmp]) tmp = idx * 2 + 1;
        if (tmp != idx){
            int t = heap[tmp];
            heap[tmp] = heap[idx];
            heap[idx] = t;
            down(tmp);
        }
    }

    public static void up(int idx){
        int tmp = idx;
        if (idx / 2 >= 1 && heap[idx / 2] > heap[tmp]) tmp = idx / 2;
        if (tmp != idx){
            int t = heap[tmp];
            heap[tmp] = heap[idx];
            heap[idx] = t;
            up(tmp);
        }
    }
}

桶排序

425. 明明的随机数

直播获奖

其他算法

349. 两个数组的交集（HashSet）

toArray()不能把Integer拆箱成int有點死亡

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //由於每個元素是唯一的 使用HashSet，把第一個數組記入hashset，如果第二個數組的元素在hashset出現過，
        //加入到arrayList， 并且把它從set中刪掉，這樣結果就是唯一的了
        HashSet<Integer> hash = new HashSet<>();
        for (int i = 0; i < nums1.length; i ++)
            hash.add(nums1[i]);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums2.length; i ++)
        {
            if (hash.contains(nums2[i])){
                list.add(nums2[i]);
                hash.remove(nums2[i]);
            }
        }
        int[] res = new int[list.size()];
        int idx = 0;
        for (int num : list)
            res[idx ++] = num;
        //List轉int[]
        return res;
    }
}

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //由於每個元素是唯一的 使用HashSet，把第一個數組記入hashset，如果第二個數組的元素在hashset出現過，
        //加入到arrayList， 并且把它從set中刪掉，這樣結果就是唯一的了
        HashSet<Integer> hash = new HashSet<>();
        for (int i = 0; i < nums1.length; i ++)
            hash.add(nums1[i]);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums2.length; i ++)
        {
            if (hash.contains(nums2[i])){
                list.add(nums2[i]);
                hash.remove(nums2[i]);
            }
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
}

350. 两个数组的交集 II（HashMap）

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        //使用哈希表
        HashMap<Integer, Integer> hash = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums1.length; i ++){
            hash.put(nums1[i], hash.getOrDefault(nums1[i], 0) + 1);
        } 
        for (int i = 0; i < nums2.length; i ++){
            if (hash.getOrDefault(nums2[i], 0) >= 1){
                hash.put(nums2[i], hash.get(nums2[i]) - 1);
                list.add(nums2[i]);
            }
        }
        int[] num = new int[list.size()];java
        int i = 0;
        for (int number : list)
        {
            System.out.println(number);
            num[i++] = number;
        }
        return num;
    }
}

三类排序[75. 颜色分类]

排序 - 图5#card=math&code=o%28n%29)

解题思路

排序 - 图6

设置ijk三个指针，[0, j - 1]代表全是0 [j, i - 1]代表全是1, [k + 1, n - 1]代表全是2

j，i是数组的起点，k是数组的终点。

**1.** 当**`nums[i] == 0, swap(nums[i], nums[j]) i++ , j ++`**(结合第二条,这样保证,a[0~j-1]都是0, a[j~i-1]都是1)

**1.** 当**`nums[i] == 1, i++`**(结合第一条，保证a[j, i - 1]都是1)

**1.** 当**`nums[i] == 2, swap(nums[i], nums[k]) k--`**(保证a[k+1 ~ n-1]都是2，由于不知道a[k]交换到a[i]的值是不是1，i不能+1)

代码

class Solution {
    public void sortColors(int[] nums) {
        //三色旗的问题
        /*
        设置ijk三个指针，[0, j - 1]代表全是0 [j, i - 1]代表全是1, [k + 1, n - 1]代表全是2
        j，i是数组的起点，k是数组的终点。
        当nums[i] == 0, swap(nums[i], nums[j]) i++ , j ++
        当nums[i] == 1, i++
        当nums[i] == 2, swap(nums[i], nums[k]) k--

        最后当i和k相遇的时候，整个数组就是[0, 0, ...,1,1,...,2,2..]
        */
        int n = nums.length;
        int i = 0, j = 0, k = n - 1;
        while (i <= k){

            if (nums[i] == 0){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                i ++; j ++;
            }
            else if (nums[i] == 1){
                i ++;
            }
            else if (nums[i] == 2){
                int tmp = nums[i];
                nums[i] = nums[k];
                nums[k] = tmp;
                k --;
            }   
            // for (int l = 0; l < n; l ++)
            //     System.out.print(nums[l]);
            // System.out.println();
        }
    }
}

自定义排序原则179. 最大数

假设a < b 的含义是ab < ba

那么最优解一定满足一个性质 ： 假设最优解是a1a2a3a4a5a6， 一定有a1 > a2 > a3 > a4 > a5 > a6

证明：

如果最优解中有a1 > a2 > a3 > a4 > a5 < a6 , 把a5 和 a6交换 a6a5 > a5a6， 此时就不是最优解。

此时还要证明，这个规则究竟能不能排序呢？

要证明一个自定义的关系可以排序，需要证明这个规则是全序关系的

排序 - 图7

ab <= ba，ba <= ab -> ab == ba
ab <= ba, bc <= ac -> ac <= ca

ab <= ba || ba <= ab是存在的

把字符串设置成数字权重，他们都是正数的.

class Solution {
    public String largestNumber(int[] nums) {

        String[] snums = new String[nums.length];
        for (int i = 0; i < nums.length; i ++)
            snums[i] = String.valueOf(nums[i]);

        Arrays.sort(snums, (String a, String b)->{
                String s1 = a + b;
                String s2 = b + a;
                 System.out.print(s2.compareTo(s1));
                return s2.compareTo(s1);
        });

        String res = new String();
        for (int i = 0; i < snums.length; i ++){
            res += snums[i];
        }
        int k = 0;
        while (k < snums.length - 1 && snums[k].equals("0")) k ++;
        return res.substring(k);
    }
}

lamda表达式和int[]、list之间的转换 56. 合并区间



class Solution {
    public int[][] merge(int[][] intervals) {
        //合并区间 先按左区间大小区间排序，然后判断en 和 下一个st的大小，如果有交集就延长ed，否则放进ans
        Arrays.sort(intervals, (int[] a, int[] b)->{
            return a[0] - b[0];
        });
        ArrayList<int[]> array = new ArrayList<int[]>();
        int st = intervals[0][0], ed = intervals[0][1]; 
        for (int i = 1; i < intervals.length; i ++)
        {
            if (ed < intervals[i][0]){
                array.add(new int[]{st, ed});
                st = intervals[i][0];ed = intervals[i][1];
            }
            else ed = Math.max(ed, intervals[i][1]);
        }
        array.add(new int[]{st, ed});

        for (int i = 0; i < array.size(); i ++)
            System.out.print(array.get(i) + " ");
        return array.toArray(new int[array.size()][2]);
    }
}

综合

快速选择 + 三类排序 + 穿插排列324. 摆动排序 II

class Solution {
    int mid = 0, midptr = 0, n = 0;
    public void wiggleSort(int[] nums) {
        //快速选择算法选出中位数mid，根据 < mid, == mid, > mid分成三类 o(n)
        //通过把三类排序这三类从小到大排序 o(n)
        // 然后把最小的一类穿插放置（保证两边的都比它大），这样求出来的一定是摆动序列 
        //直接排序可以吗 可以 o(nlogn)
        int l = 0, r = nums.length - 1;
        n = nums.length;
        int k = n / 2 - 1;
        midptr = quickSelect(l, r, k, nums);
        if (n != 1 && n % 2 == 1) midptr++;
        mid = nums[midptr];
        //通过荷兰旗把这三类从小到大排序 o(n) 
        three_partition(nums);
        intersperse(nums);
    }
    int quickSelect(int l, int r, int k, int[] nums){
        if (l == r) return l;
        int i = l - 1, j = r + 1;
        int mid = nums[l + r + 1>> 1];

        while (i < j){
            do i++; while (nums[i] < mid);
            do j--; while (nums[j] > mid);
            if (i < j){
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        if (k >= i) return quickSelect(i, r, k, nums); 
        else return quickSelect(l, i - 1, k, nums);
    }

    //三类排序
    void three_partition(int[] nums){
        int i = 0, j = 0, k = n - 1;
        //中止条件是 i = k + 1
        while (i <= k){
            //0~j - 1 是第一类
            if (nums[i] < mid){int t = nums[j]; nums[j] = nums[i]; nums[i] = t; i++;j++;}
            //j~i - 1是第二类
            else if (nums[i] == mid){i++;}
            // k+1~n-1是第三类
            else {int t = nums[k]; nums[k] = nums[i]; nums[i] = t;k--;}
        }
        // for ( i = 0; i < n; i ++)
        //     System.out.print(nums[i] + " ");
    }
    void intersperse(int[] nums){
        //拆分，后半段数组反序
        List<Integer> pre = new ArrayList<Integer>();
        for (int i = midptr; i >= 0; i --) pre.add(nums[i]);
        List<Integer> post = new ArrayList<Integer>();
        for (int i = n - 1; i > midptr; i --) post.add(nums[i]);
        //间隔插入
        for (int i = 0; i < post.size(); i ++){
            nums[i * 2] = pre.get(i);
            nums[i * 2 + 1] = post.get(i);
        }
        if (n % 2 == 1) nums[n - 1] = pre.get(n / 2);
    }
}