我在我的一项作业中遇到了这个问题。我已经尝试找出解决方案几个小时,但似乎我做错了什么。
我需要根据数字的频率对数组进行排序,例如;
[-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 是混合的。我该如何解决这个问题?也许我应该尝试一些完全不同的东西?
编辑:我不知道如何使用链表,我不确定我们是否可以使用我们所学之外的任何东西。
最佳答案
一种策略是计算元素的二维数组的出现次数,并对这个新数组进行排序。
对于二维数组,我声明了一个类 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;
}
关于java - 按频率排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48250327/