LCR 075. 数组的相对排序

孤寂灬无痕字数: 5615 阅读耗时: 14 分钟 2025/07/29 博客独享热度: 6 评论:

给定两个数组，arr1 和 arr2，

arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

提示：

1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中

思路

数组集合+Comparator实现
手动实现快排变体
统计学魅力时刻

代码

数组集合+Comparator实现

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //数组排序
        int[] order = new int[1001];
        int index = -arr2.length;
        for (int i : arr2) {
            order[i] = index;
            index++;
        }
        //集合
        List<Integer> list = new ArrayList<>(arr1.length);
        for (int i : arr1) {
            list.add(i);
        }
        list.sort((o1, o2) -> {
            int x = o1;
            int y = o2;
            if (order[o1] != 0) {
                x = order[o1];
            }
            if (order[o2] != 0) {
                y = order[o2];
            }
            return x - y;
        });
        //数组排序
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}

手动实现快排变体

class Solution {
    //LCR 075. 数组的相对排序
    private int[] order;

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //手动实现sort
        order = new int[1001];
        for (int i = 0; i < 1001; i++) {
            order[i] = i;
        }
        int index = -arr2.length;
        for (int i : arr2) {
            order[i] = index;
            index++;
        }
        dualPivotQuickSort(arr1, 0, arr1.length - 1);
        return arr1;
    }

    // 双轴快速排序核心实现
    private void dualPivotQuickSort(int[] array, int left, int right) {
        if (left < right) {
            // 确保pivot1 <= pivot2
            if (order[array[left]] > order[array[right]]) {
                swap(array, left, right);
            }

            int pivot1 = order[array[left]];
            int pivot2 = order[array[right]];

            int i = left + 1;
            int k = left + 1;
            int j = right - 1;

            // 分区过程
            while (k <= j) {
                if (order[array[k]] < pivot1) {
                    swap(array, k, i);
                    i++;
                } else if (order[array[k]] >= pivot2) {
                    while (order[array[j]] > pivot2 && k < j) {
                        j--;
                    }
                    swap(array, k, j);
                    j--;
                    if (order[array[k]] < pivot1) {
                        swap(array, k, i);
                        i++;
                    }
                }
                k++;
            }

            i--;
            j++;

            // 将枢轴放到正确位置
            swap(array, left, i);
            swap(array, right, j);

            // 递归排序三个子区间
            dualPivotQuickSort(array, left, i - 1);
            dualPivotQuickSort(array, i + 1, j - 1);
            dualPivotQuickSort(array, j + 1, right);
        }
    }

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

统计学魅力时刻

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int index = 0;
        int [] hash = new int [1001];
        for (int n : arr1) {
            hash[n]++;
        }
        for (int n : arr2) {
            while (hash[n]-- > 0) {
                arr1[index++] = n;
            }
        }
        for (int n = 0; n < hash.length; ++n) {
            while (hash[n]-- > 0) {
                arr1[index++] = n;
            }
        }
        return arr1;
    }  
}