Finding repeating numbers in an array

Question

I want to search through an array of n numbers and find the numbers that are repeated. So far I have this code, which does the job, but I find it to be a rather cumbersome method, but I can't seem to find another method of doing it.

class Checknumber{
    int [] numbers = new int [5];
    Scanner inn = new Scanner(System.in);
    boolean b = true;
    int temp = -1;

    void sjekk(){
        System.out.println("Write five numbers");
        for(int i = 0; i < numbers.length; i++){
        numbers [i] = inn.nextInt();
    }

    //sjekker om det er like tall i arrayen
    System.out.print("\nNumbers that are repeated: ");
    for(int i = 0; i < numbers.length; i++){

        if(!b){
            System.out.print(temp + " ");
        }

        b = true;
        temp = numbers[i];
        for(int j = 0; j < numbers.length; j++){
            if(i != j && temp == numbers[j] && numbers[j] != -2){
                b = false;
                numbers[j] = -2;
            }
        }
    }

}

Answer 1

int[] numbers = { 1, 5, 23, 2, 1, 6, 3, 1, 8, 12, 3 };
Arrays.sort(numbers);

for(int i = 1; i < numbers.length; i++) {
    if(numbers[i] == numbers[i - 1]) {
        System.out.println("Duplicate: " + numbers[i]);
    }
}

This sorts the array numerically, then begins iterating the array. It checks the previous element in the array and if it equals the current element, then you have a duplicate.

Answer 2

Others have given alternate solutions. However, since this is Code Review, I'll offer a critique instead, because I think you will learn more from that than by just seeing the answer.

Interfaces

• Checknumber is too vague. I suggest DuplicateNumberDetector.
• In your interfaces (class and method names), pick either English or Norwegian and stick with it. For your comments, use whatever language works for you.
• sjekk() (meaning "check") is actually responsible for receiving input rather than performing the checking. How misleading!

Variables

• b is very poorly named. I suggest unique instead.
• temp is somewhat poorly named. I suggest num instead.
• Only older dialects of C require you to declare all variables at the top. Java lets you declare variables near the point of first use. You should take advantage of that. int temp should be declared inside the for (i) loop, since it is never used outside the loop.
• You might try to pull the declaration of b inside the for (i) loop too. But then you will realize that b refers to the uniqueness of the previous numbers[i]. That reveals a bug: what if the last two numbers are identical (numbers[3] == numbers[4], but numbers[2] != numbers[3])? You haven't handled the termination case correctly. Hint: Move your print statement. The lesson to be learned here is that declaring temporary variables far from the point of use is almost as evil and dangerous as using global variables.

Logic

• You are using -2 as a special value to indicate that an array element has already been detected as a duplicate. That's bad because your code will fail if -2 happens to be one of the inputs.
• Overwriting the input array is a surprising side effect. That's as unforgivable as sending your computer to a repair shop to install a video card and getting it back with the hard drive reformatted. If you really need to overwrite the input, state so clearly in a comment. You should be able to find a solution to this problem that does not require overwriting.
• Your inner loop has j going from 0 to the end of the array. That means you are handling every pair twice. You should probably be able to start from i + 1 instead, to reduce your processing in half. Handling each pair only once should simplify your logic as well.

Efficiency

• You have two for loops, each iterating over the entire array. If the array has n elements, then the run time for your algorithm is O(n²). (Even with the inner-loop optimization mentioned in the previous point, it would still be O(n²).) For a small homework problem like this, that is perfectly acceptable, because simplicity is the main goal. If you wanted to handle very large arrays, though, it would be more efficient to sort the input first or use a HashMap.

Separation of concerns

• Your input, processing, and output code are all intertwined. Get into the habit of separating them. Your code will be more reusable and easier to understand.

.

public class DuplicateNumberDetector {  
    int[] promptInputs(int numberOfInputs) { ... }

    // If the order doesn't matter, use Set<Integer> instead
    List<Integer> findDuplicates(int[] numbers) { ... }

    void printDuplicates(List<Integer> dups) { ... }

    public static void main(String[] args) {
        printDuplicates(findDuplicates(promptInputs(5)));
    }
}

Answer 3

I'm gonna throw my 2 cents in aswell :)

If you're allowed to used objects I'd do it like this.

Sets automatically holds non-duplicates so if it contains it it's no chance of the value going in a again.

int[] arrayOfInt = { 1, 2, 3, 5, 1, 2, 7, 8, 9, 10 };
Set<Integer> notDupes = new HashSet<Integer>();
Set<Integer> duplicates = new HashSet<Integer>();
for (int i = 0; i < arrayOfInt.length; i++) {
    if (!notDupes.contains(arrayOfInt[i])) {
        notDupes .add(arrayOfInt[i]);
        continue;
    }
    duplicates.add(arrayOfInt[i]);
}
System.out.println("num of dups:" + duplicates.size());
System.out.println("num of norls:" + notDupes.size());

Answer 4

Create a Map<Integer, Integer> (first number is the number you are looking, second is the number of appearences).

Run through your array. Each time you find a number, do map.get(numberFound) to see if you had already found it. If you had not, put the number with a counter of 1. If you had, retrieve the counter, increase it and put it back into the map.

Answer 5

I would use Set for this logic:

1. Create an empty Set MySet, and another empty Set ResultSet.

2. Read each number and perform this on it:

   1. Check if it is in MySet.
   2. If it's in MySet, then put it in ResultSet.
   3. If it's not in MySet, then put it in Myset.

3. ResultSet contains the required numbers.

The benefit of this approach is that the complexity would reduce from O(n²) to O(nlog(n)).

Answer 6

This is almost the easiest way! hashSet returns false whenever a duplicate number is added to it.

private static void findDuplicateNumber() {
    Set<Integer> hashSet = new HashSet<Integer>();

    for(int i=0; i < arr.length; i++){
        boolean unique = hashSet.add(arr[i]);
        if(unique == false)
            System.out.println("duplication " + arr[i]);
    }      

}

Answer 7

you may use google collection framework Guava's Multiset<Integer> to find repetating number.

Elements of a multiset that are equal to one another (see "Note on element equivalence", below) are referred to as occurrences of the same single element. The total number of occurrences of an element in a multiset is called the count of that element (the terms "frequency" and "multiplicity" are equivalent, but not used in this API). Since the count of an element is represented as an int, a multiset may never contain more than Integer.MAX_VALUE occurrences of any one element.

Multiset<Integer> set = HashMultiset.create();
void sjekk(){
        System.out.println("Write five numbers");
        for(int i = 0; i < numbers.length; i++){
        set.add(inn.nextInt());
    }
...
for(Multiset.Entry<Integer> entry : set.entrySet()){ 
 System.out.println("Element :-> "+entry.getElement()+" Repeat Cnt :-> "+entry.getCount());
}