Removing dups from array

[Kevin Behr]

Hey everyone,

Given a sorted array (of ints), I need to change the array so that any integer that appears only once will appear at the beginning of the SAME array, and still in a sorted order. Also, the program's running time should be proportional to the array (so I cannot have one loop nested inside another loop).

I have done this. However, there is some flaw in my code such that for the following array:

{0,2,2,3,3,7,9,11,11}

My output is:

{0,2,4,7,9}

So, it's not including the last 11. In my attempts to fix this, I have been recieving some out-of-bounds errors. I think I've just been looking at the code for too long. Can anyone see the problem? Here is my code:

public class rem_dups {

	static int[] A = new int[10];

	public static void initialize_array() {

		A[0] = 0;
		A[1] = 2;
		A[2] = 2;
		A[3] = 2;
		A[4] = 4;
		A[5] = 4;
		A[6] = 7;
		A[7] = 9;
		A[8] = 11;
		A[9] = 11;

	}

	public static void main(String[] args) {
		int i, j;

		j = 0;

		initialize_array();

		for (i = 1; i < A.length; i++) {
			if (A[i] != A[j]) {
				j++;			
				A[j] = A[i];	// Move it to the front
			}
		}

		System.out.println("length: " + j);	// Length of the "no duplicate segment"
		System.out.println();
		for (i = 0; i < j; i++) {
			System.out.println("A[" + i + "] = " + A[i]);
		}
	}
}

Thanks!

[Jeanne Boyarsky]

 for (i = 1; i < A.length; i++) {  
             if (A[i] != A[j]) {  
                 j++;              
                 A[j] = A[i];    // Move it to the front  
             }  
         }  

Kevin,
In this code, things are set so that j will always be one more than i at the end of the loop. The problem being in the line with the comment "move it to the front." If j is one higher than i and i is the last element in the array, there's no element there.

Think about what you want to do if the last element is the duplicate. Can you say it in a sentence?

[Rob Spoor]

I don't think that's the problem. The thing is, j always points to the last assigned element. That means that the length of the sub array is not j, but j + 1. If I change the for loop guard to "i <= j" I see the 11. If I change A[9] to 13, I see that 13 as well.

[Ganesh Gowtham]

Hi Kevin ,

let me know your view on the below code .

String[] input = {"0","2","2","3","3","7","9","11","11"};		
		Set<String> set = new HashSet<String>(Arrays.asList(input));
		for (String element : set) {
			System.out.println(element);
		}

I think it will easy,simple and uses Util classes .

[Rob Spoor]

If you use a LinkedHashSet instead of a HashSet, you preserve the order and that would be a viable solution. It still runs in linear time (O(n)), because the adding of the array (as list) is linear; the check whether or not the element exists takes constant time (O(1)) because of the hashing.

Still, if this were a homework assignment, I doubt you would get much credit for it. I would add it as an addendum to show how easy it can be, but the professor would probably want to see your own algorithm. And that's just what Kevin has done, albeit with a minor bug.

[Campbell Ritchie]

Not convinced about the use of a Set, because the output was supposed to be ordered. Also I think he is supposed to work out the algorithm himself.

[Ganesh Gowtham]

Hi Rob i agree with you regarding the maintaining the order .

Preserving Order

  

String[] input = {"0","2","2","3","3","7","9","11","11"};		
		Set<String> set = new LinkedHashSet<String>(Arrays.asList(input));
		for (String element : set) {
			System.out.println(element);
		}
  

Sorting....

  

String[] input = {"0","2","2","90","90","7","9","1","1"};		
		Set<String> set = new TreeSet<String>(Arrays.asList(input));
		for (String element : set) {
			System.out.println(element);
		}
  

[Kevin Behr]

Hey guys,

Thanks for all of your replies! I greatly appreciate it.

Ganesh: Nice implementation, but unfortunately I can't use it. Campbell is right in that I have to work out the algorithm. The reason being is that I am taking a "Formal Methods and Models" class, in which we derive programs (mathematically). I'm working backwards to understand the problem more (and because I'm awful at math!).

Rob, you were right, by changing the < to a <= in the second for loop, the 11 appeared. I test a couple more sets, and things seem to be working well!

Now that I understand what the program should look like, I have to derive it from a loop invariant that was given to me

Thanks again!

[Rob Spoor]

You should actually have done it the other way around. Given a pre condition, post condition and loop invariant, you should be able to write the program.

Could you please tell us what these are? We may be able to help you. We won't give you full solutions though.

[Kate Terlecka]

Hi,

your program calculates everything correctly - it's just that you're not writing the last element to the output. You should write that up to j, not j-1 :

		for (i = 0; i <= j; i++) {
			System.out.println("A[" + i + "] = " + A[i]);

Kate T.