如何在不使用Java中的Arrays类(例如，不排序)的情况下找到数组中最频繁的值

Question

此代码用于在每个给定的数据集中查找统计模式。

public double mode() {
if(data==null) {
return Double.NaN;
}
else if(data.length==0) {
return Double.NaN;
}
else {
int[] counter1=new int[data.length];
int counter2=0;
double mode = Double.NaN;
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data.length; j++) {
if (data[i] == data[j]) {
counter1[i]++;
}
else {
}
}
}for(int i=0; i<data.length; i++) {
for (int j=0; j < data.length; j++) {
if (counter1[i] > counter1[j]) {
counter2=i;
}
}
}
if (counter2 > 0) {
mode = data[counter2];
}else if (counter2 < 0){
mode = Double.NaN;
}
return mode;
}

使用以下数据集：

1. [20.00，20.0]
2. [1.0、2.0、3.0、4.0、5.0、6.0、7.0]

我希望获得可变模式：

For dataset 1: mode=20.0 
For dataset 2: mode=NaN

但是，我得到的是：

For dataset 1: mode=NaN
For dataset 2: mode=NaN

我应该如何实现这个结果，并拥有每次将正确的统计模式保存到变量模式的方法？

免责声明：我不能使用任何Helper方法(例如Array(

Answer 1

你可以试试这个：

public static Double getPopularElement(double[] a) {
int count = 1, tempCount;
double popular = a[0];
double temp;
boolean isUnique = false;
for (int i = 0; i < (a.length - 1); i++) {
temp = a[i];
tempCount = 0;
for (int j = 1; j < a.length; j++) {
if (temp == a[j])
tempCount++;
}
if (tempCount > count) {
isUnique = true;
popular = temp;
count = tempCount;
} else if (tempCount == count) {
isUnique = false;
}
}
return isUnique ? popular : Double.NaN;
}

测试运行：

{1.0, 2.0, 3.0} == NaN
{1.0, 3.0, 2.0, 2.0, 3.0} == NaN
{1.0, 3.0, 2.0, 3.0} == 3.0

Answer 2

测试：

[20.0, 20.0] = 20.0
[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0] = NO MODE
[1.0, 2.0, 3.0, 8.0, 4.0, 3.0, 5.0, 6.0, 7.0, 6.0] = [3.0, 6.0]
[4.0, 5.0, 4.0, 5.0] = [4.0, 5.0]
[-1.0, 2.0, -1.0, 2.0] = [-1.0, 2.0]

代码：

public class Mode {
public static void main(String[] args) {
double test1[] = { 20.0, 20.0 };
double test2[] = { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0 };
double test3[] = { 1.0, 2.0, 3.0, 8.0, 4.0, 3.0, 5.0, 6.0, 7.0, 6.0 };
double test4[] = { 4.0, 5.0, 4.0, 5.0 };
System.out.println(getMode(test1));
System.out.println(getMode(test2));
System.out.println(getMode(test3));
System.out.println(getMode(test4));
}
private static String getMode(double arr[]) {
double checked[] = new double[arr.length];
int occurrences[] = new int[arr.length];
for (int i = 0; i < arr.length; ++i) {
if (!arrayContains(checked, arr[i])) {
checked[i] = arr[i];
occurrences[i] = arrayCount(arr, arr[i]);
}
}
int lowest[] = sorted(occurrences, true);
int highest[] = sorted(occurrences, false);
if (arraysEqual(lowest, highest) && highest.length > 1) {
return "NO MODE";
}
int j = 0;
Double modes[] = new Double[arr.length];
int most_occurrence = highest[0];
for (int i = 0; i < occurrences.length; ++i) {
if (occurrences[i] == most_occurrence) {
modes[j++] = arr[i];
}
}
double result[] = removeNullValues(modes);
return result.length == 0 ? "Error" : result.length > 1 ? arrayToString(result) : Double.toString(result[0]);
}
private static boolean arrayContains(double arr[], double value) {
return arrayCount(arr, value) > 0;
}
private static int arrayCount(double arr[], double value) {
int count = 0;
for (int i = 0; i < arr.length; ++i) {
if (arr[i] == value) {
++count;
}
}
return count;
}
private static boolean arraysEqual(int a[], int b[]) {
if (a.length != b.length) {
return false;
}
for (int i = 0; i < a.length; ++i) {
if (a[i] != b[i]) {
return false;
}
}
return true;
}
private static double[] removeNullValues(Double arr[]) {
Double result[] = new Double[arr.length];
int j = 0;
for (int i = 0; i < result.length; ++i) {
if (arr[i] != null) {
result[j++] = arr[i];
}
}
// trim array
double realResult[] = new double[j];
for (int i = 0; i < j; ++i) {
realResult[i] = result[i];
}
return realResult;
}
private static void sort(int arr[], boolean ascending) {
int t = 0;
for(int i = 0; i < arr.length; ++i) {
for(int j = 0; j < arr.length - 1; ++j) {
if (ascending ? arr[j + 1] < arr[j] : arr[j + 1] > arr[j]) {
t = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = t;
}
}
}
}
private static int[] sorted(int arr[], boolean ascending) {
int result[] = new int[arr.length];
for (int i = 0; i < arr.length; ++i) {
result[i] = arr[i];
}
sort(result, ascending);
return result;
}
public static String arrayToString(double[] a) {
int iMax = a.length - 1;
if (iMax == -1) {
return "[]";
} else {
String res = "[";
int i = 0;
while(true) {
res += a[i];
if (i == iMax) {
return res + "]";
}
res += ", ";
++i;
}
}
}
}

Answer 3

下面的解平均为O(nlog(n((。

其想法是首先对数组进行排序，然后只需迭代一次即可找到重复次数最多的数字。

public static Double getMostFrequentElement(double[] a) {
quickSort(a, 0, a.length-1); // Instead of Arrays.sort(a); O(nlog(n))
return getMostFrequentElementInSortedArray(a); // O(n)
}
private static double getMostFrequentElementInSortedArray(double[] sortedArr) {
if(sortedArr.length == 0){
return Double.NaN;
}else if(sortedArr.length == 1){
return sortedArr[0];
}
int maxCount = 1, currCount = 1;
double result = Double.NaN, curr = sortedArr[0];
for (int i = 1; i < sortedArr.length; i++) {
if (curr == sortedArr[i]) {
currCount++;
if (currCount == maxCount) {
result = Double.NaN;
} else if (currCount > maxCount) {
result = curr;
maxCount = currCount;
}
} else {
curr = sortedArr[i];
currCount = 1;
}
}
return result;
}
// Sorting
public static void quickSort(double[] arr, int begin, int end) {
if (begin < end) {
int partitionIndex = partition(arr, begin, end);
quickSort(arr, begin, partitionIndex-1);
quickSort(arr, partitionIndex+1, end);
}
}
private static int partition(double[] arr, int begin, int end) {
double pivot = arr[end];
int i = (begin-1);
for (int j = begin; j < end; j++) {
if (arr[j] <= pivot) {
i++;
double swapTemp = arr[i];
arr[i] = arr[j];
arr[j] = swapTemp;
}
}
double swapTemp = arr[i+1];
arr[i+1] = arr[end];
arr[end] = swapTemp;
return i+1;
}

输出示例：

getMostFrequentElement(new double[]{20.0, 20.0}); // 20.0
getMostFrequentElement(new double[]{1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0}); // NaN
getMostFrequentElement(new double[]{1.0, 2.0, 2.0, 3.0, 1.0, 1.0}); // 1.0
getMostFrequentElement(new double[]{2.0, 1.0, 2.0, 3.0, 1.0, 1.0}); // 1.0
getMostFrequentElement(new double[]{3.0, 2.0, 2.0, 1.0, 1.0, 2.0}); // 2.0
getMostFrequentElement(new double[]{1.0, 2.0, 3.0, 1.0, 5.0, 6.0, 7.0}); // 1.0
getMostFrequentElement(new double[]{2.0, 2.0, 3.0, 1.0, 5.0, 6.0, 7.0}); // 2.0
getMostFrequentElement(new double[]{2.0, 5.0}); // NaN
getMostFrequentElement(new double[]{2.0}); // 2.0
getMostFrequentElement(new double[]{}); // NaN