按频率排序

Question

按频率排序

javasorting

3

我在我的作业中遇到了一个问题。我已经尝试了好几个小时来找出一个解决方案，但似乎我做错了什么。

我需要按数字出现的频率对数组进行排序，例如;

[-1.1, -1.1, 2.4, -3.0, 4.0, 2.4, -1.1, -3.0] => [-1.1, -1.1, -1.1, 2.4, 2.4, -3.0, -3.0, 4.0]

[-0.5, 4.0, 6.5, 6.5, 4.0, -0.5] => [-0.5, -0.5, 4.0, 4.0, 6.5, 6.5]

我尝试过的方法是创建一个名为count()的函数，该函数检查数组中某个double值出现的次数，然后返回该数量。

然后我编写了一个函数:

public static void sortByFreq(double[] arr)

    public static void sortByFreq(double[] arr)
{   
    double temp;
    for(int i = 0; i < arr.length; i++)
    {
        for(int j = 0; j < arr.length; j++)
        {

            if(count(arr, arr[i]) > count(arr, arr[j])) 
            {
// swap them if one of them appears more times(its count is bigger)
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;

            }

        }

    }

    for(int i = 0; i < arr.length; i++) // print the numbers
    {
        System.out.print(arr[i] + " ");
    }


}

使用这种方法，我设法得到了一个不完整的答案，例如第一个例子可以很好地计算并正确打印。但是第二个例子输出 [-0.5, 4.0, 6.5, 6.5, 4.0, -0.5] => [-0.5, 4.0, 6.5, 6.5, 4.0, -0.5]，你可以看到4.0和6.5混合在一起了。我该如何解决这个问题？也许我应该尝试完全不同的方法？编辑：我不知道如何使用链表，而且我不确定是否允许我们使用除所学内容以外的任何东西。

- michelle fanter

为什么不直接输入 Arrays.sort(array) 呢？ - Basil Battikhi

为什么在只关注数量的情况下需要进行排序？ - Basil Battikhi

2个回答

0

这是因为您得到了两个具有相同频率的不同数字。如果频率相等，则必须比较数字本身。只需将您的if条件从排序更改为以下内容：

if(count(arr, arr[i]) >= count(arr, arr[j]) && arr[i] < arr[j]) {           
       temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
}

- Schidu Luca

嘿，这个好像不对。[-0.5, 4.0, 6.5, 6.5, 4.0, -0.5] => [-0.5, -0.5, 4.0, 4.0, 6.5, 6.5]，但是我得到的是[6.5, 6.5, 4.0, 4.0, -0.5, -0.5]，我忘了提到它们应该按照谁先来进行排序。 - michelle fanter

2

@michellefanter，那是一个非常重要的编辑...你应该把它放到问题中。 - Eugene

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel R. · Accepted Answer

一种策略是计算出现次数，创建一个元素的二维数组并对该新数组进行排序。

对于这个二维数组，我声明了一个名为Element.java的类。

public class Element{ 

    public int count;
    public int index;
    public double val;

    public Element(int index, int count , double val){
        this.count = count;
        this.index = index;
        this.val = val;
    }

}

主要用于按频率对数组进行排序的算法如下：

public static void sortByFrequency(double arr[]) {
    Element[] elements = new Element[arr.length];
    for (int i = 0; i < elements.length; i++)
        elements[i] = new Element(i,0,arr[i]);

    /* Count occurrences of remaining elements */
    for (int i = 0; i < arr.length; i++) {
        for(int j = 0; j < arr.length; j++){
            if(elements[i].val == elements[j].val)
                elements[i].count++;
        }
    }
    /* sort on the basis of count and in case of tie use index
    to sort.*/
    Arrays.sort(elements, new Comparator<Element>() {
        @Override
        public int compare(Element o1, Element o2) {
            if (o1.count > o2.count) return -1;
            else if (o1.count < o2.count) return 1;
            // tie breaker
            if(o1.count == o2.count ){
                if (o1.val > o2.val) return -1;
                else if (o1.val < o2.val) return 1;
            }
            return 0;
        }
    });

    for (int i = 0; i < arr.length; i++)
        arr[i] = elements[i].val;
}