0

Possible Duplicate:
Java Array, Finding Duplicates

I have this array

int[][] array = {{1,2,3,4}, {5,6,2,8}, {9, 10, 11, 12}, {13, 14, 15, 16}};

If there are duplicate elements in this array, i need to return false. For example index [0][1] and [1][2] are equal. I need a method that detects this. Also it would be nice if the solution only used primitives, arrays, and loops.

Improve this question
3
  • So you have 64 * 64 iterations there?? Noticed that? Commented Dec 13, 2012 at 20:27
  • @Natix More likely stairway to hell Commented Dec 13, 2012 at 20:39
  • @Natix and Tomas -- Guys don't make fun of him, help him instead of discouraging to resolve his issue. Commented Dec 13, 2012 at 20:49

6 Answers 6

Reset to default
5

1: Add all values to a List (e.g ArrayList)
2: add all to a set (e.g TreeSet)

compare list.size() to set.size()

if not equal, than you have dupplicates

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

7 Comments

Beated me to it by a few secs. As a comment, to avoid adding everything you can do a single loop to add the elements from the list to the set and return true (meaning "there are duplicates") if theSet.add() return false.
@AlexWien, Its really nice way to resolve issue. But take a look at his code, do you really think he will be able to do this.
Why do you even need step 1, this solution doesn't take advantage of early exiting
@Gamb the set.add() method would be the answer I'd vote up. The first instance where it returns false could be the stopping condition. no need for the list at all.
I would just add them to a set and skip the list. ;)
|
4

If you only want to use primitives you can use TIntHashSet like this

TIntHashSet set = new TintHashSet(); // like Set<Integer> but with primitives
for(int[] arr: array) for(int i: arr) if(!set.add(i)) return false;
return true;

The set.add method returns false if the value could not be added as it's a duplicate.

Improve this answer

4 Comments

TIntHashSet is a primitive? Do I have the right link?
Nice, but a solution using an external library is not the way to go, except for 1 million entries.
TInHashSet is not a primitive nor is the int[] it wraps but it avoid creating Integers or Entry objects like HashSet would. I agree that a plain HashSet<Integer> should be considered first.
Thanks for the solution. I've modified it a little bit so as to not use an external library. I changed: TIntHashSet set = new TintHashSet(); to: Set<Integer> set = new HashSet<Integer>();
1

I think its a homework question, so no actual implementation only guidelines.

  1. You need 2 for loops only as you have 2D array.

  2. Iterate through all numbers in your array and compare them for their equality.

  3. If any duplicate found return false.

Another way

  1. Convert this 2D array to 1D array

  2. Iterate and compare all values

Improve this answer

2 Comments

This does not work. You need to pick the first index and compare it to every other. Then pick then pick the second and compare it to every other again, and so on... This simply would not work with 2 loops.
@user1253722 I updated the answer will this help you or not let me know?
1

Try below code 

package com.rais.duplicates;

import java.util.HashSet;
import java.util.Set;

/**
 * @author Rais.Alam
 * @date Dec 14, 2012
 */
public class DetectDuplicateClient
{

    public static boolean isDuplicate(int[][] array)
    {
        boolean retVal = false;
        if (array != null && array.length > 0)
        {
            Set<Integer> temp = new HashSet<Integer>();

            outer:
            for (int[] innerArray : array)
            {
                for (int value : innerArray)
                {
                    if(!temp.add(value))
                    {
                        retVal = true;
                        break outer;
                    }

                }
            }
        }
        return retVal;
    }

    public static void main(String[] args)
    {

        int[][] array =  { { 1, 2, 3, 4 }, { 5, 6, 2, 8 }, { 9, 10, 11, 12 },{ 13, 14, 15, 16 } };

        System.out.println(isDuplicate(array));
    }

}
Improve this answer

Comments

0

Pseudocode:

  1. Loop through all values, adding them to a HashSet
  2. At each iteration, check to see if the Set contains that element. If it does, return false immediately.
  3. return true;.

Here's another way that works only if you know the maximum element

  1. Create a new array, where each cell in the array is indexed by the element
  2. If the array cell is zero, increment the cell (cell[element]++).
  3. If the array cell is 1, return false;.
  4. return true;
Improve this answer

Comments

0

My solution:

  1. 2D array elements to a list
  2. Sort the list
  3. Check in one for loop if i indexed list item == i + 1
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.