I'm trying to solve an algorithm question. I need to find a single integer in an array
e.g {1,1,5,5,5,3,2,2}
output should 3 because that's the only single integer there.
So far, I created an algorithm where first I sort the array and then check whether i-1 and i+1 elements are equal and if not it means I've got the single one.
The issue is; for short input it's working fine but for long inputs I receive time-outs (it takes too long to compute so my answer is not validated).
Could you give me any tips for improving the algorithm
static int lonelyinteger(int[] a) {
Arrays.sort(a);
if (a.length == 1)
return a[0];
for (int i = 0; i < a.length; ++i) {
if (i == 0) {
if (a[i + 1] != a[i])
return a[i];
} else if (i == a.length - 1) {
if (a[i] != a[i - 1])
return a[i];
} else {
if (a[i - 1] != a[i] && a[i + 1] != a[i])
return a[i];
}
}
return -1;
}
Is O(N^2) not considered "fast enough" for this problem?
Here I have a list of 10,000,000 elements with random pair values. In a random spot, I put the "lonely integer" 5, and O(N^2) solves it quickly without the need to sort. The algorithm stops on the first "lonely integer" it finds.
public static void main(String[] args) {
Random r = new Random();
List<Integer> ints = new ArrayList<>();
for (int i = 0; i < 10000000; i += 2) {
int randomNumber = r.nextInt(100) + 10;
ints.add(randomNumber);
ints.add(randomNumber);
}
ints.add(5); // Lonely Integer
int tempIndex = r.nextInt(ints.size());
int tempValue = ints.get(tempIndex);
// Swap duplicate integer with lonely integer
ints.set(tempIndex, ints.get(ints.size() - 1));
ints.set(ints.size() - 1, tempValue);
for (int i = 0; i < ints.size(); i++) {
boolean singleInteger = true;
for (int j = 0; j < ints.size(); j++) {
if (j == i) {
continue;
}
if (ints.get(j) == ints.get(i)) {
singleInteger = false;
break;
}
}
if (singleInteger) {
System.out.println("Single instance: " + ints.get(i));
break;
}
}
}
Results:
Single instance: 5 (about 10 - 20 seconds);
Your method about 3 seconds.
Map solution...
public static void main(String[] args) {
Random r = new Random();
List<Integer> ints = new ArrayList<>();
for (int i = 0; i < 10000000; i += 2) {
int randomNumber = r.nextInt(100) + 10;
ints.add(randomNumber);
ints.add(randomNumber);
}
ints.add(5); // Lonely Integer
int tempIndex = r.nextInt(ints.size());
int tempValue = ints.get(tempIndex);
// Swap duplicate integer with lonely integer
ints.set(tempIndex, ints.get(ints.size() - 1));
ints.set(ints.size() - 1, tempValue);
Map<Integer, Integer> counts = new HashMap<>();
for (int i : ints) {
if (counts.containsKey(i)) {
counts.put(i, counts.get(i) + 1);
} else {
counts.put(i, 1);
}
}
for (Integer key : counts.keySet()) {
if (counts.get(key) == 1) {
System.out.println("Single Instance: " + key);
}
}
}
Results:
Single Instance: 5 (about 1 - 3 seconds)
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments