在Java中循环计算数组中整数的出现次数

Question

注意：无映射，无排序

这是我的密码：

public static void countArray(int[] n){
    int[] m = new int[n.length]; //50 elements of integers between values of 10 & 20
    int count = 0;
    int sum = 0;

    for ( int i = 0; i < n.length ; i++){
        m[i] = n[i]; //make a copy of array 'n'
        System.out.print(m[i]+" ");

    }System.out.println();

    for ( int j =0; j < n.length ; j++){
        count =0;
        for(int i = 0; i < n.length ; i++){
            if (n[j]%m[i]==0 && n[j] == m[i])
                count++;
        }if ( n[j]%m[j] == 0)
        System.out.println(m[j] + " occurs = " + count);
    }   
}

所以问题是：我在不同的行上得到重复的结果，比如：“25发生=5”

我的想法：问题的出现是因为if ( n[j]%m[j] == 0) 所以我试了一下。另一个问题发生了，因为m[j]将是m[50]，所以它崩溃了，但某种程度上给了我想要的结果

我想要的结果是：类似这样：不重复，覆盖集合上的所有随机整数

17 occurs = 3
23 occurs = 2
19 occurs = 3
15 occurs = 2
12 occurs = 2

Answer 1

这里有一个很好的、有效的方法，比这里发布的其他解决方案更有效。这一个在O（n）时间内运行，其中数组的长度为n。它假设您有一些数字MAX_VAL，表示在数组中可能找到的最大值，最小值为0。在你的评论中，你建议MAX_VAL==20

public static void countOccurrences(int[] arr) {
    int[] counts = new int[MAX_VAL+1];
    //first we work out the count for each one
    for (int i: arr)
        counts[i]++;
    //now we print the results
    for (int i: arr)
        if (counts[i]>0) {
            System.out.println(i+" occurs "+counts[i]+" times");
            //now set this count to zero so we won't get duplicates
            counts[i]=0;
        }
}

它首先在数组中循环，每次找到元素时增加相关计数器。然后它返回，并打印出每一个的计数。但是，至关重要的是，每次打印一个整数的计数时，它都会将该整数的计数重置为0，这样就不会再次打印

如果您不喜欢for (int i: arr)样式，那么这是完全等效的：

public static void countOccurrences(int[] arr) {
    int[] counts = new int[MAX_VAL+1];
    //first we work out the count for each one
    for (int i=0; i<arr.length; i++)
        counts[arr[i]]++;
    //now we print the results
    for (int i=0; i<arr.length; i++)
        if (counts[arr[i]]>0) {
            System.out.println(arr[i]+" occurs "+counts[arr[i]]+" times");
            //now set this count to zero so we won't get duplicates
            counts[arr[i]]=0;
        }
}

Answer 2

如果利用输入限制，则可能会丢失嵌套循环：

public static void main(String[] args)
{
    //6 elements of integers between values of 10 & 20
    int[] countMe = { 10, 10, 20, 10, 20, 15 };

    countArray(countMe);
}

/** Count integers between values of 10 & 20 (inclusive) */
public static void countArray(int[] input)
{
    final int LOWEST = 10;
    final int HIGHEST = 20;

    //Will allow indexes from 0 to 20 but only using 10 to 20
    int[] count = new int[HIGHEST + 1]; 

    for(int i = 0; i < input.length; i++)
    {
        //Complain properly if given bad input
        if (input[i] < LOWEST || HIGHEST < input[i])
        {
            throw new IllegalArgumentException("All integers must be between " +
                    LOWEST + " and " + HIGHEST + ", inclusive");
        }

        //count
        int numberFound = input[i]; 
        count[numberFound] += 1;
    }

    for(int i = LOWEST; i <= HIGHEST; i++)
    {
        if (count[i] != 0) 
        {
            System.out.println(i + " occurs = " + count[i]);
        }
    }
}   

Answer 3

通过一些调整，您的代码应该可以工作：

public static void countArray(int[] n){
    boolean [] alreadyCounted = new boolean[n.length]; 

    for (int i = 0; i < n.length ; i++){
        int count = 0;
        if (alreadyCounted[i]) {
            // skip this one, already counted
            continue;
        }
        for(int j = 0; j < n.length ; j++){
            if (n[i] == n[j]) {
                // mark as already counted
                alreadyCounted[j] = true;
                count++;
            }
        }
        System.out.println(n[i] + " occurs = " + count);
    }   
}

你完全可以用同样的逻辑来编写更好的代码，我只是试着遵循最初的“编码风格”

这是O（n^2）解决方案（请阅读“非常慢”）
如果您可以使用排序，那么您可以在O（n log（n））中进行排序-即快速
有了映射，你可以在O（n）中完成它，这是非常快的

Answer 4

尝试：（对数组排序，然后计算元素的出现次数）

public static void countArray(int[] n) {
    int count = 0;
    int i, j, t;
    for (i = 0; i < n.length - 1; i++) // sort the array
    {
        for (j = i + 1; j < n.length; j++) {
            if (n[i] > n[j]) {
                t = n[i];
                n[i] = n[j];
                n[j] = t;
            }

        }
    }

    for (i = 0; i < n.length;)
    {
        for (j = i; j < n.length; j++) {
            if (n[i] == n[j])
            {
                count++;
            } else
                break;
        }
        System.out.println(n[i] + " occurs " + count);
        count = 0;
        i = j;

    }

}