排序

特殊元素排序

75. 颜色分类 mid

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

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

荷兰国旗问题
可以遍历 2 次, 一次交换 0, 一次交换 1;
也可以遍历 1 次, 有多种解法, 都是利用多个指针处理;

解法 1 双指针 0,1

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, p1 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                swap(nums, i, p1);
                p1++;
            } else if (nums[i] == 0) {
                swap(nums, i, p0);
                // 如果 p0 < p1, 说明 [p0] = 1, 刚刚的交换会将 1 换到 i 的位置, 需要将其放在 1 序列的末端
                if (p0 < p1) swap(nums, i, p1);
                p0++;
                p1++; // 0 序列变长了, p1 也要++
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

解法 2 双指针 0,2

维护三个指针, 一个是 0 的目标位, 一个是 2 的目标位, 还有一个是索引, 索引前面没有 2

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0; // 0 的 待填充位置
        int i = 0; // 索引
        int p2 = nums.length - 1; // 2 的待填充位置
        // i 前面没有 2
        while (i <= p2) {
            switch (nums[i]) {
                case 2 -> {
                    // 将 2 交换到 p2; 交换后 [i] 是未知的, 所以 i 不动
                    if (nums[p2] != 2) swap(nums, i, p2);
                    p2--;
                }
                case 0 -> {
                    // 将 0 交换到 p0; [p0] != 2, 原因是 i >= p0, 2已经交换到 p2 了
                    if (nums[p0] != 0) swap(nums, i, p0);
                    p0++;
                    i++;
                }
                default -> i++;
            }
        }
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

解法 3 双指针 0,2

这种解法跟解法 2 语意上是一样的

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; i++) {
            while (i <= p2 && nums[i] == 2) {
                swap(nums, i, p2);
                p2--;
            }
            if (nums[i] == 0) {
                swap(nums, i, p0);
                p0++;
            }
        }
    }
    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

283. 移动零 easy

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

将 !=0 的元素移动到左指针前, 左右指针之间[)的都是 0

class Solution {
    public void moveZeroes(int[] nums) {
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                swap(nums, i, idx);
                idx++;
            }
        }
    }
}

665. 非递减数列 mid

给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

class Solution {
    public boolean checkPossibility(int[] nums) {
        if (nums.length <= 2) return true;
        int cnt = 0;
        // 核心: 让迭代中的尾部(3个元素)尽可能小
        for (int i = 1; i < nums.length && cnt < 2; i++) {
            if (nums[i] >= nums[i - 1]) continue;
            cnt++;
            // 前2个 改[0]
            if (i == 1) {
                nums[i - 1] = Integer.MIN_VALUE;
                continue;
            }
            if (nums[i] >= nums[i - 2])
                // 如果[0]<[2] 改[1]
                // 2 4 3 => 2 2 3
                nums[i - 1] = nums[i - 2];
            else
                // [0]>=[2] 改[2]
                // 2 4 1 => 2 4 4
                nums[i] = nums[i - 1];
        }
        return cnt <= 1;
    }
}

922. 按奇偶排序数组 II easy

给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案。

无额外空间排序, 交换

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] ^ i) % 2 != 1) continue;
            int j = i + 1;
            while ((nums[j] ^ i) % 2 == 1) j++;
            swap(nums, i, j);
        }
        return nums;
    }

    void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

按条件排序

406. 根据身高重建队列 mid

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

解法 预排序+重建

低的对高的没有贡献, 所以从高到低排序, 这样低的可以直接插
如果高度相同, 按 k 排序, 后面的不会插到前面

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
        List<int[]> list = new ArrayList<>(people.length);
        for (int[] o : people) {
            list.add(o[1], o);
        }
        return list.toArray(new int[people.length][]);
    }
}

451. 根据字符出现频率排序 mid

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

解法 计数+排序

map 计数, 然后排序

class Solution {
    public String frequencySort(String s) {
        int[] cntMap = new int[128];
        for (char c : s.toCharArray()) {
            cntMap[c]++;
        }
        PriorityQueue<Character> que = new PriorityQueue<>((a, b) -> cntMap[b] - cntMap[a]);
        for (char i = 0; i < 128; i++) {
            if (cntMap[i] > 0) que.add(i);
        }
        StringBuilder res = new StringBuilder();
        while (!que.isEmpty()) {
            Character c = que.remove();
            res.append(String.valueOf(c).repeat(cntMap[c]));
        }
        return res.toString();
    }
}

953. 验证外星语词典 easy

LCR 034. 验证外星语词典

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

class Solution {
    // order
    int[] map = new int[128];

    public boolean isAlienSorted(String[] words, String order) {
        char[] arr = order.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            map[arr[i]] = i;
        }
        for (int i = 1; i < words.length; i++) {
            if (!less(words[i - 1], words[i])) return false;
        }
        return true;
    }

    boolean less(String s1, String s2) {
        int i = 0, j = 0;
        while (i < s1.length() && j < s2.length()) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(j);
            if (map[c1] < map[c2]) return true;
            if (map[c1] > map[c2]) return false;
            i++;
            j++;
        }
        return s1.length() <= s2.length();
    }
}

合并

88. 合并两个有序数组 mid

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应忽略。nums2 的长度为 n。

反向合并, 不会覆盖;
三个指针

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 从尾到头的索引
        int x = nums1.length - 1;
        for (int i = m - 1, j = n - 1; x >= 0; x--) {
            if (i >= 0 && j >= 0) {
                if (nums1[i] > nums2[j]) nums1[x] = nums1[i--];
                else nums1[x] = nums2[j--];
            }
            else if (i >= 0) nums1[x] = nums1[i--];
            else if (j >= 0) nums1[x] = nums2[j--];
            else break;
        }
    }
}

排序算法

快排

1. quicksort 函数重载，参数（待排序数组，前后两个 index）
2. 递归 sort，到 2 个 index 相等为止
3. partition 是重点
4. 选主元, 取首尾中三个数的中位数放到倒数第二位;（在考虑性能的情况下）

 新建两个指针不断地向前向后遍历，找到比主元大/小的停下等待交换；

public class QuickSort {

    public static void main(String[] args) {
        QuickSort sort = new QuickSort();
        int[] ints = new int[]{1, 3, 2, 5, 8, 6, 7, 4};
        sort.quickSort(ints);
        System.out.println(Arrays.toString(ints));
    }


    void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    void quickSort(int[] arr, int low, int high) {
        if (high <= low) return;
        int index = partition(arr, low, high);
        quickSort(arr, low, index - 1);
        quickSort(arr, index + 1, high);
    }

    int partition(int[] arr, int low, int high) {
        int i = low;
        int j = high + 1; // j会先执行减减操作，预留一个+1
        int pivot = arr[low];
        for (; ; ) {
            // 不断地做交换，直到两个指针碰撞为止; 相同也停下来做交换
            // 前面的判断条件主要是为了防止数组下标越界
            while (i < high && arr[++i] < pivot) ;
            while (j > low && arr[--j] > pivot) ;
            if (i >= j) break;
            exchange(arr, i, j);
        }
        // 此时 arr[j] <= pivot，arr[i] >= pivot，并且 j<=i; 做交换
        exchange(arr, low, j);
        return j;
    }

    void exchange(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}