Finding repeating numbers in an array

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

    }

    You should tag the language you're using.

    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" ?

    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.

    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"

    Please, everybody here, use for-each; this is 2013, not 2003. for(int i: numbers) { } Please, eliminate one trivial source of error.

    If you're facing a big data situation, cardinality estimation (http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation) is a probabilistic way of figuring out how many unique (or repeated) items are in a dataset.

  • Phil K

    Phil K Correct answer

    8 years ago
    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.


    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)

    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.

    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)`.

    You've modified the original array, which might not have been wanted. Creating a sorted copy would be polite.

    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?).

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM