时间戳

首页 > 解决方案 > 我需要帮助以这种特殊方式根据频率对 java 中的数组进行排序

java - 我需要帮助以这种特殊方式根据频率对 java 中的数组进行排序

问题描述

需要帮助获取一个数组，计算频率，放入另一个数组，数组索引作为数字，单个值作为 Java 中的频率

您可以使用包含 n 个条目的数组计数来计算数组中每个整数出现的次数，从而对范围为 1 到 n 的 m 个整数组成的大型数组进行排序。例如，考虑以下由 14 个整数组成的数组 A，范围从 1 到 9（请注意，在这种情况下 m = 14 且 n = 9）：

9 2 4 8 9 4 3 2 8 1 2 7 2 5

形成一个包含 9 个元素的数组 count，使得 count[i-1] 包含 i 在要排序的数组中出现的次数。因此，计数是

1 4 1 2 1 0 1 2 2

尤其是，

使用count数组对原数组A进行排序。在函数中实现这个排序算法

public static void countingSort(int[] a, int n )

并根据 m（数组 a 的长度）和 n 分析其最坏情况下的运行时间。调用countingSort() 后，a 必须是排序数组（不要将排序结果存储在临时数组中）。

编辑：这是我尝试过的

 public static void countingSort1(int[] a, int n) {
    int [] temp = new int[n];
    int [] temp2 = new int[n];
    int visited = -1;
    for (int index = 0; index < n; index++) {
        int count = 1;
        for (int j = index +1; j < n; j++) {
            if(a[index] == a[j]) {
                count++;
                temp[j] = visited;
            }

        }
        if (temp[index]!= visited) {
            temp[index] = count;
        }
    }
    for(int i = 1; i < temp.length; i++) {
        if (temp[i] != visited) {
            System.out.println("  " +a[i] + "  |   " +temp[i]);
        }
    }

只是为了计算频率，但我认为我做错了

标签： javafrequency

解决方案

像下面这样的东西应该可以完成工作：

  • 由于您已经知道最高值是多少，在您的示例 9 中，创建一个包含九个元素空间的频率数组。
  • 遍历您的输入数组，并为您找到的每个值将您的频率数组中值的索引处的值增加一
  • 为索引创建一个计数器并将其初始化为 0
  • 在嵌套循环中迭代您的频率数组，并将输入数组中的值替换为频率数组的索引。

我把复杂性的分析留给你

public static void countingSort(int[] a, int n ){
    //counting
    int[] freq = new int[n];
    for(int i = 0; i<a.length; i++){
        freq[a[i]-1]++;
    }
    //sorting
    int index = 0;
    for(int i = 0; i< freq.length; i++){
        for(int j = 0;j < freq[i];j++){
            a[index++]= i+1;                
        }            
    }
    System.out.println(Arrays.toString(a));
}

推荐阅读