Imagine that you have a TreeSet
of numbers, and you copy them into an array, but you remove one element of it. You want to know the element removed.
import java.util.Arrays;
import java.util.Set;
import com.google.common.collect.Sets;
public class Question {
private static final Set<Integer> SET = Sets.newTreeSet(Arrays.asList(1, 3, 5, 7));
public static void main(String[] args) {
int[] unsorted = {1, 5, 3};
int elementRemoved = checkElementRemoved(unsorted);
System.out.println("Element removed " + elementRemoved);
}
private static int checkElementRemoved(final int[] unsorted) {
Integer elementRemoved = null;
for (Integer number : SET) {
if (!arrayContains(unsorted, number)) {
// O(n^2) complexity
elementRemoved = number;
break;
}
}
return elementRemoved;
}
private static boolean arrayContains(final int[] unsorted, final int number) {
for (Integer inArray : unsorted) {
if (inArray == number) {
return true;
}
}
return false;
}
The problem is that this solution has \$O(n^2)\$ complexity and I would like to improve the performance.
I think that the best option would be to sort the array, am I right?