"move to" gets the index to the 4th position, since that's the location to which you're going to copy the next unique element. If your array contained a b c c c d e f f f g, then you compare a b, b c, and finally c c (in 3rd and 4th positions) and discover you have a duplicate. The "move to" index is not defined until you actually find duplicates. As a matter of fact, after you find your first duplicate, it is *always* going to be moved, and I call it the "copy from" index. the second, "move to", points to the next location where you want the next unique value to go, and the third points to the next value to compare to the "compare to" value, which is also the value that may be moved. I see three indices: one points to the value you "compare to", i.e., the first of the two numbers being compared. J- // to check the element j+2, which now becomes j+1 and would be skipped otherwiseĪrr = new ArrayIns(maxSize) // create the array Public void display() // displays array contentsįor(int j=0 j0 & a >= temp) // until one is smaller,įor(int i = 0 i < nElems i++) // set loop to step throughįor(int j = i+1 j Ideas?Īnd obviously, no, I can not use hashSets or bitsets or or any other built-in class or data structure different than an array. However, there must be a simpler/less-confusing-to-code way to do it. My naive way of doing this is to first locate all the duplicates in the array and replace said duplicates with null values, and then shift the elements to the left according to the number of nulls I get. My goal is to make sure no item is moved more than once, no matter how many duplicates there are (this will give O(N) time). One can imagine schemes in which all the items from the place where a duplicate was discovered to the end of the array would be shifted down one space every time a duplicate was discovered (I wrote the methods noDups() and its helper, delete(), to do exactly this), but this leads to O(N2) time, at least when there were a lot of duplicates. My class consists of wrapped long array that uses insertion sort to sort its elements. So I have the assignment of adding a method to remove duplicates from an ordered array.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |