面试算法75:数组相对排序

发布时间:2023年12月28日

题目

输入两个数组arr1和arr2,其中数组arr2中的每个数字都唯一,并且都是数组arr1中的数字。请将数组arr1中的数字按照数组arr2中的数字的相对顺序排序。如果数组arr1中的数字在数组arr2中没有出现,那么将这些数字按递增的顺序排在后面。假设数组中的所有数字都在0到1000的范围内。例如,输入的数组arr1和arr2分别是[2,3,3,7,3,9,2,1,7,2]和[3,2,1],则数组arr1排序之后为[3,3,3,2,2,2,1,7,7,9]。

分析

题目明确提出数组中的数字都在0到1000的范围内。这是一个很明显的提示,据此可以考虑采用计数排序。先统计数组[2,3,3,7,3,9,2,1,7,2]中每个数字出现的次数,发现数字1出现了1次,2出现了3次,3出现了3次,7出现了2次,以及9出现了1次。接下来根据数组[3,2,1]确定的数字顺序,先后输出3个3、3个2、1个1。由于还剩下数字7和9,因此再按照大小输出2个7和1个9。

public class Test {
    public static void main(String[] args) {
        int[] arr1 = {2, 3, 3, 7, 3, 9, 2, 1, 7, 2};
        int[] arr2 = {3, 2, 1};
        int[] result = relativeSortArray(arr1, arr2);
        for (int item : result) {
            System.out.println(item);
        }
    }

    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] counts = new int[1001];
        for (int num : arr1) {
            counts[num]++;
        }

        int i = 0;
        for (int num : arr2) {
            while (counts[num] > 0) {
                arr1[i++] = num;
                counts[num]--;
            }
        }

        for (int num = 0; num < counts.length; num++) {
            while (counts[num] > 0) {
                arr1[i++] = num;
                counts[num]--;
            }
        }
        return arr1;
    }
}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135268564
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。