Java - Finding the least common integer in a sorte

问题:

I was assigned a programming problem for homework, and I am at a stand-still. I have searched for hours today trying to find an answer, and it seems like it's never been asked on here. I basically need to find the reverse of the mode of the array. Here is the question I was asked to find the solution to:

LeastFrequent - Output the integer which occurs least frequently along with its occurrence count from a list of 10 integers input from System.in. If multiple integers in the list occur least frequently, output any integer that occurs least frequently. Name your class LeastFrequent. You can assume that all 10 integers are in the range -100 to 100 inclusive.

Here is the code I have so far:

package leastfrequent;
import java.util.*;

public class LeastFrequent
{
    private static int[] arr = new int[10];
    private static int minValue;
    private static int minCount;

    public static void leastCommon()
    {
        for(int i = 0; i < arr.length; i++)
        {
            int count = 0;

            for(int j = 0; j < arr.length; j++)
            {
                if(arr[j] == arr[i]) 
                {
                    count++;
                }
            }

            if(count > minCount)
            {
                minCount = count;
                minValue = arr[i];
            }
        }
    }

    public static void main(String[] args)
    {
        Scanner stdin = new Scanner(System.in);
        System.out.print("numbers: ");

        for(int i = 0; i < arr.length; i++)
        {
            arr[i] = stdin.nextInt();
        }

        Arrays.sort(arr);
        leastCommon();

        System.out.println("least frequent: " + minValue + " occurs " + minCount + " times");
    }
}

Basically I figured if I could find the mode, I could reverse that algorithm and find the least common, but that doesn't work because it always reads zero.

Does anyone have any ideas?

Please help!!

回答1:

Two changes:

1. Initialize minCount with biggest index i.e. 10 as:

   private static int minCount = 10;
   

2. Change the if to compare against less than in place of greater than as:

   if(count < minCount){
   

This way you will change the minCount with lower count, whenever you receive the lower occurence count and in the end, it will have the least.

I think, rest is fine. Hope this fixes your program.

回答2:

You can use an auxiliary array of length 201 since your range is [-100,100].

int[] counters = new int[201];

Suppose user entered -59, increment that specific counter: (You should add 100 to the entered number to find index, think of -100 is at index 0)

counters[-59 + 100]++;

Then iterate over the counters array and find the smallest non-zero element. Subtract 100 from that index, and that is the least frequent number surely.

int  min = Integer.MIN_VALUE;

for(int i: counters)
{
   if(i != 0 && i < min)
     min = i;
}

Now, it means that counters[i] has occured least frequent, which corresponds (i-100) in actual value.

回答3:

Think about how you'd do this with pen and paper.

1. Count the number of times each number appears in the array.
2. Find the smallest count.
3. Return the value corresponding to that count. This demands that you somehow stored the value mapped to its count.

The fact that the array is sorted allows you to optimize this algorthm by looking for the shortest consecutive run of equal numbers. That means you can do this in a single pass, with O(1) auxiliary memory.