Monday, November 9, 2009

Extracting unique element(s) from a sorted list

PROBLEM: you have a list of sorted elements. All elements are sorted (it could be in ascending order or descending order). You are printing out the unique elements in the sorted list.
COMPLEXITY: O(n)

public class UniqueNumbers {
public static void main(String[] args) {
int a[]={1, 1, 1, 2, 4, 4, 7, 8, 9, 14, 14, 20, 20, 20};
//int a[]={1};
//int a[]={2, 2, 4, 5};
//int a[]={1, 1, 1, 2, 2, 8};
//int a[]={1, 1, 1};
int uniq = a[a.length-1];
boolean numberExists = false;
for (int i = 0; i < a.length; i++) {
if (a[i] == uniq) {
if (!numberExists) {
System.out.println("Position: " + i + " Unique Element => " + a[i]);
numberExists = true;
}
}
else {
System.out.println("Position: " + i + " Unique Element => " + a[i]);
uniq = a[i];
numberExists = true;
}
}
}
}
The output is shown below:

{1, 1, 1, 2, 4, 4, 7, 8, 9, 14, 14, 20, 20, 20}
Position: 0 Unique Element => 1
Position: 3 Unique Element => 2
Position: 4 Unique Element => 4
Position: 6 Unique Element => 7
Position: 7 Unique Element => 8
Position: 8 Unique Element => 9
Position: 9 Unique Element => 14
Position: 11 Unique Element => 20

{1}
Position: 0 Unique Element => 1

{2, 2, 4, 5}
Position: 0 Unique Element => 2
Position: 2 Unique Element => 4
Position: 3 Unique Element => 5

{1, 1, 1, 2, 2, 8}
Position: 0 Unique Element => 1
Position: 3 Unique Element => 2
Position: 5 Unique Element => 8

{1, 1, 1}
Position: 0 Unique Element => 1
Update: my solution is not that elegant after all. I had the opportunity to discuss the algorithm with Mark and he has a much better way to solve this problem. Thank you, Mark (you know who you are :D).

public static void main(String[] args) {
int a[]={1, 1, 1, 2, 4, 4, 7, 8, 9, 14, 14, 20, 20, 20};
//int a[]={1};
//int a[]={2, 2, 4, 5};
//int a[]={1, 1, 1, 2, 2, 8};
//int a[]={1, 1, 1};
int uniq = a[0];
System.out.println("Position: " + 0 + " Unique Element => " + uniq);
for (int i = 1; i < a.length; i++) {
if (a[i] != uniq) {
System.out.println("Position: " + i + " Unique Element => " + a[i]);
uniq = a[i];
}
}
}

2 comments:

  1. I guess line 17 can be replaced with 'else'
    and, in general, it would be nice to see the output generated by your programs.

    ReplyDelete
  2. sure :)
    thank you for your comment.

    yupe, using a "else" is reasonable.
    I'll post the output of the algorithm soon.

    ReplyDelete