Databases
StackOverflow2013
Postsdbo
PORemoving duplicates from a sorted int[] using binarysearch
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PORemoving duplicates from a sorted int[] using binarysearch
    text
    copied!<p>I have a rather large int[] which is sorted using <code>Arrays.sort()</code> .. I need to remove the duplicate elements from the array.</p> <p>This question originates from sedgewick's Algorithms book 1.1.28 </p> <blockquote> <p>1.1.28 Remove duplicates. Modify the test client in BinarySearch to remove any du- plicate keys in the whitelist after the sort.</p> </blockquote> <p>I tried to create a noDupes() method which takes in an int[] and returns an int[] with duplicates removed</p> <p>The rank() methods are from sedgewick's code.which does the binary search</p> <pre><code>public static int[] noDupes(int[] a){ Arrays.sort(a); int maxval= a[a.length-1]; int[] nodupes = new int[maxval]; int i=0; for(int j=0;j&lt;a.length;j++){ int rnk = rank(a[j],nodupes); System.out.println(a[j]+" rank="+rnk); if (rnk &lt; 0){ System.out.println(a[j]+" is not dupe"); nodupes[i] = a[j]; i++; } } return nodupes; } public static int rank(int key,int[] a){ return rank(key,a,0,a.length-1); } public static int rank(int key,int[] a,int lo,int hi){ if(lo &gt; hi) return -1; int mid = lo+(hi-lo)/2; if(key &lt; a[mid])return rank(key,a,0,mid-1); else if(key &gt; a[mid])return rank(key,a,mid+1,hi); else return mid; } </code></pre> <p>When I ran this with a sample array </p> <pre><code>int[] a =new int[]{2,2,2,3,4,4,5,6}; int[] ret = noDupes(a); </code></pre> <p>I am getting some unexpected output..even after 2 is added to the nodupes array, the rank for an existing element is -1..</p> <pre><code>2 rank=-1 2 is not dupe 2 rank=-1 2 is not dupe 2 rank=-1 2 is not dupe 3 rank=-1 3 is not dupe 4 rank=-1 4 is not dupe 4 rank=4 5 rank=-1 5 is not dupe 6 rank=-1 6 is not dupe Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6 at ...noDupes(BinSearch.java:85) at ...main(BinSearch.java:96) </code></pre> <p>I couldn't figure out what I am doing wrong..can someone help?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload