Check to see if any duplicate index values exist within an array?

Question

So basically, I have one array, with ten values...

int[] input = new int[10];

The user controls the input to each value.

What would be a good technique to check to see if any of the values inside of the array are equal to any of the other values?

Edit:

public static void main(String[] args) {
    P2 numbers = new P2();

    for (int i = 0; i < numbers.input.length; i++) {
        numbers.input[i] = numbers.scan.nextInt();
    }
    numbers.Check();
    if (numbers.Check()) { System.out.println("Duplicate"); }
    if (numbers.Check() == false) { System.out.println("NOT Duplicate"); }
}

public boolean Check() {
        int length = input.length;
        for(int i : input) {
            for(int j = i + 1; j < length; j++) {
                if(input[i] == input[j]) return true;
            }
        }
        return false;
    }

The codes works ask long as duplicate numbers are index-neighbors.

StriplingWarrior · Accepted Answer · 2011-02-01 23:34:53Z

8

If you really only have ten values in the array, you're better off with a double-nested loop that breaks when it finds a duplicate.

int length = input.length;
for(int i = 0; i < length; i++) {
    for(int j = i + 1; j < length; j++) {
        if(intput[i] == input[j]) return true;
    }
}

If you're expecting to scale up to a large number, you're better off populating a hashset and breaking when you find a value that's already in the Hashset.

HashSet<Integer> set = new HashSet<Integer>();
for(int i : input) {
    if(set.contains(i)) return true;
    set.add(i);
}

edited Feb 1, 2011 at 23:34

answered Feb 1, 2011 at 23:22

StriplingWarrior

158k29 gold badges261 silver badges326 bronze badges

Sign up to request clarification or add additional context in comments.

15 Comments

Stephen Denne Over a year ago

i is being given input values, but then used as an index.

Hanna Over a year ago

` for(int j = i + 1; j < length; j++)` won't this for loop only check the index right above the previous one?

Stephen Denne Over a year ago

A BitSet would be much more efficient for finding duplicate ints.

StriplingWarrior Over a year ago

@Johannes: it will only check the indices after the current i value. This does two things: it avoids getting a false positive by checking array[1] against itself, and it cuts the number of comparisons in half because if you know array[1] != array[2], then you can assume array[2] != array[1].

StriplingWarrior Over a year ago

@Johannes: You'd follow the same general pattern as the second code sample (with the HashSet), but the first line of the for loop would be if(!set.contains(i)) System.out.println(i);. If you want to do both (print non-duplicates, then return true if there were duplicates), you'd have to use a boolean variable to track whether you had encountered a duplicate, which would only be slightly more complex. I personally wouldn't combine the two, though.

|

Sören · Accepted Answer · 2011-02-01 23:25:27Z

1

You could

compare all values in two loops (inefficient)
sort the array and then only compare adjacent values. This is more efficient, especially for longer arrays.

The first one is very easy to implement and if your array only has a length of 10, this should suffice.

answered Feb 1, 2011 at 23:25

Sören

2,7512 gold badges20 silver badges23 bronze badges

Comments

Stephen Denne · Accepted Answer · 2011-02-02 00:09:30Z

1

If the stored int values are small non-negative values, then a BitSet might be appropriate:

BitSet set = new BitSet();
for(int i : input) {
    if(set.get(i)) return true;
    set.set(i);
}

If you instead have a wide range of values, and lots of them, but a low likelihood of there being a duplicate (i.e. you expect there to be no duplicates, and simply need to confirm that), you can hash the ints, and use a BitSet(8192) of the low 13 bits of the hash (for example). That only uses roughly 1k. This can be used to easily confirm that there are no duplicates, but if it does find a hash collision, then you need to re-check with a less efficient method.

edited Feb 2, 2011 at 0:09

answered Feb 1, 2011 at 23:50

Stephen Denne

37.2k10 gold badges49 silver badges61 bronze badges

Comments

Ted Hopp · Accepted Answer · 2011-02-01 23:25:06Z

0

You can also sort the array and scan quickly for duplicates. Compared to building a hashset, it won't use as much memory, but will be slower.

answered Feb 1, 2011 at 23:25

Ted Hopp

235k48 gold badges412 silver badges533 bronze badges

Collectives™ on Stack Overflow

Check to see if any duplicate index values exist within an array?

4 Answers 4

15 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

15 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related