6
\$\begingroup\$

I am interested in printing all numbers that do not have a match in an array.
Example: 1,3,4,5,3,4,5,5,6 result 1,5,6
Please review my solution bellow. What would be a much better way for this? Any input on how to improve this is welcome

public static Integer[] outputSinglePair(Integer[] numbers){  
        if(numbers == null)  
            throw new IllegalArgumentException();  

        Arrays.sort(numbers);  
        ArrayList<Integer> result = new ArrayList<Integer>();  
        for(int i = 0; i < numbers.length - 1; ){  
            if(numbers[i] != numbers[i + 1]){  
                result.add(numbers[i]);  
                i++;                
            }     
            else  
                i+=2;  
            if(i == numbers.length - 1)result.add(numbers[i]);//we hit last element of array which is unpaired
        }  
        return result.toArray(new Integer[0]);  
    }  
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Are you sure that you have phrased this question correctly? "am interested in printing all numbers that do not have a match in an array." Based on your input, 1 appears once, 3 appears twice, 4 appears twice, 5 appears thrice, and 6 appears once. I would expect that only numbers 1 and 6 appear in the result set yet you have included 5. Can you please clarify? \$\endgroup\$ – Tony R Jun 13 '12 at 15:26
8
\$\begingroup\$

I think this is the sort of thing for which HashSet is perfect. Your implementation would look something like I have shown below. The advantage is that you don't need a sort so your running time is strictly linear.

(Updated to fix syntax errors)

public static Integer[] outputSinglePair(Integer[] numbers){  
    if(numbers == null)
        throw new IllegalArgumentException();

    HashSet<Integer> result = new HashSet<Integer>();
    for (int next: numbers) {
        if (result.contains(next)) {
            result.remove(next);
        }
        else {
            result.add(next);
        }
    }
    return result.toArray(new Integer[result.size()]);
}  
\$\endgroup\$
2
  • \$\begingroup\$ It doesn't work if number exists in the array 3, 5, and etc (odd number) times. \$\endgroup\$ – anstarovoyt Jun 1 '12 at 4:25
  • \$\begingroup\$ Actually, it does work for odd number times. When you have three of something - first one goes into result, second one takes it out, third puts it back in. I tested it just to make sure (and fix a couple of syntax errors). \$\endgroup\$ – Donald.McLean Jun 1 '12 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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