17
\$\begingroup\$

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;
            }
        }
    }

}
\$\endgroup\$
6
  • \$\begingroup\$ You should tag the language you're using. \$\endgroup\$
    – Asad
    Nov 23, 2012 at 15:19
  • \$\begingroup\$ Do you mean dupplicate numbers, or a set of identical numbers in a series? Should that eliminate the last "1" in "1231", or the "3" in "12333333456" ? \$\endgroup\$
    – AlexWien
    Nov 23, 2012 at 15:27
  • 1
    \$\begingroup\$ Another possibility is to sort the array first, for example using Arrays.sort(). This would bring any repeated numbers next to each other, simplifying the logic needed to find and print them out. \$\endgroup\$
    – NPE
    Nov 23, 2012 at 15:28
  • \$\begingroup\$ I should have been more clear. If I have a set "1 2 3 2 1" then I want the program to print out: "These numbers are repeating: 1 and 2" \$\endgroup\$ Nov 24, 2012 at 0:44
  • \$\begingroup\$ Please, everybody here, use for-each; this is 2013, not 2003. for(int i: numbers) { } Please, eliminate one trivial source of error. \$\endgroup\$
    – itsbruce
    Aug 23, 2013 at 15:18

7 Answers 7

12
\$\begingroup\$
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.

\$\endgroup\$
5
  • 4
    \$\begingroup\$ Best readable. A small suggestion: Add a while(i < numbers.length && numbers[i] == numbers[i - 1]) ++i; behind the if statement in the loop to prevent multiple output (according to original behavior) \$\endgroup\$
    – tb-
    Nov 23, 2012 at 17:48
  • 1
    \$\begingroup\$ Thank you all for answering! I'm very new to programming, so I haven't learned such functions as sort yet, so I see now that there are much easier ways of doing it. I tried this code and it works, however if there are more than two numbers in the array that are similar, it will print that number n-2 times times the number of repetitions within the array. I didn't manage to incorporate the small suggestion below. \$\endgroup\$ Nov 24, 2012 at 0:39
  • \$\begingroup\$ This isn't the most optimal, but it's fast enough. Also, there should probably be a check for multiple duplicates. I would expect [1, 1, 1, 2, 3] to only output "Duplicate: 1". This is trivial to implement: if (numbers[i] == numbers[i - 1] && numbers[i] != lastDup). \$\endgroup\$
    – beatgammit
    Nov 24, 2012 at 8:42
  • \$\begingroup\$ You've modified the original array, which might not have been wanted. Creating a sorted copy would be polite. \$\endgroup\$
    – itsbruce
    Aug 23, 2013 at 14:54
  • \$\begingroup\$ The biggest problem I have with this solution is that it won't scale to very large n (because you have to hold the entire array in memory at once). But it's an elegant solution for relatively small n (< 1,000,000?). \$\endgroup\$
    – Graham
    Mar 5, 2014 at 18:51
13
\$\begingroup\$

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(n2). (Even with the inner-loop optimization mentioned in the previous point, it would still be O(n2).) 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)));
    }
}
\$\endgroup\$
0
7
\$\begingroup\$

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());
\$\endgroup\$
3
  • 1
    \$\begingroup\$ +1, but you don not know how duplicate you have for a number, so use Map<Integer,Integer> duplicates; = .. and int nbDuplicat = (int) duplicates.get(xNumber) and duplicates.put( nbDuplicat == 0 ? 1 : nbDuplicat++) - You can also if (!notDupes .add(arrayOfInt[i]);) { continue; } duplicates.add(arrayOfInt[i]); becaus it it cannot add it, it return false \$\endgroup\$
    – cl-r
    Nov 23, 2012 at 16:20
  • \$\begingroup\$ That was not apart of the question, though. \$\endgroup\$ Nov 23, 2012 at 16:50
  • 1
    \$\begingroup\$ you are right! but my experience in true life have guessed than it will be asked soon, \$\endgroup\$
    – cl-r
    Nov 24, 2012 at 16:43
5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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(n2) to O(nlog(n)).

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'd rather just use one set or array as I like to make programs that use as little memory as possible, but I will try this for fun! \$\endgroup\$ Nov 24, 2012 at 0:41
  • \$\begingroup\$ The space complexity is still N :D \$\endgroup\$ Nov 24, 2012 at 1:17
  • 1
    \$\begingroup\$ @HatoriSanso "I'd rather just use one set or array as I like to make programs that use as little memory as possible" Please be careful about Premature Optimiation! It is good that you are trying to be efficient but realize that 'efficient' in computer terms could mean many things (memory is just the tip of the iceberg). When in doubt: 1. Make it work 2. Make it right 3. Make it fast (aka optimize) -Kent Beck \$\endgroup\$
    – Tony R
    Nov 25, 2012 at 4:39
  • \$\begingroup\$ and just to add my 2 cents, if you want to optimise, always calculate the space and time complexity, not just how many copies it uses. In my solution, two copies will be used for n elements( 2n ), and in your solution 1 copy will used (1n) , but the space complexity is same N , so it wont matter much. It is only a issue when you increase the complexity to NlogN or N^2. Also your solution has time complexity of N^2, and the one I wrote has worst case NlogN , so it is more efficient. Two copies of data dont affect space complexity/efficiency. \$\endgroup\$ Nov 25, 2012 at 5:12
3
\$\begingroup\$

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]);
    }      

}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You should use if (!unique) {... } instead of if(unique == false). Good spotting. \$\endgroup\$
    – rolfl
    Mar 24, 2014 at 14:36
  • \$\begingroup\$ int[] arr should be a parameter to this function. (Surely it's not a static member of the class, right?) \$\endgroup\$ Mar 24, 2014 at 16:02
  • \$\begingroup\$ It would be better to use new-style for loops: for (int a : arr) { ... }. \$\endgroup\$ Mar 24, 2014 at 16:03
0
\$\begingroup\$

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());
}
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.