01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
// Exercise 1.1.28
package algs11;
import stdlib.*;
import java.util.Arrays;

/*
   1.1.28 Remove duplicates.
   Modify the test client in BinarySearch to remove any duplicate keys in the whitelist after the sort.

   Hint: For this problem, you will need to create a second array that is
   smaller than the original whitelist.  You need to go through the
   original whitelist twice.  The first time, you need to determine the number
   of unique items in the whitelist; use this as the size of the second array,
   which you create.  The second time, copy the unique items to the new
   array.
 */
public class MyBinarySearchRemoveDuplicates {

  // precondition: array a[] is sorted
  public static int rank (int key, int[] a) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
      // key is in a[lo..hi] or not present.
      int mid = lo + (hi - lo) / 2;
      if (key < a[mid]) hi = mid - 1;
      else if (key > a[mid]) lo = mid + 1;
      else return mid;
    }
    return -1;
  }

  // precondition: array a[] is sorted
  public static int[] removeDuplicates (int[] a) {
    int N = a.length;
    if (N < 1) return a;

    // determine number of unique elements
    // TODO

    // copy from a to new array
    // TODO
    return null;
  }

  public static void printRemoveDuplicates (int[] a) {
    //StdOut.println (Arrays.toString (a));
    StdOut.println (Arrays.toString (removeDuplicates (a)));
  }

  public static void testRemoveDuplicates () {
    printRemoveDuplicates (new int[] {});
    printRemoveDuplicates (new int[] {10});
    printRemoveDuplicates (new int[] {10, 10});
    printRemoveDuplicates (new int[] {10, 20});
    printRemoveDuplicates (new int[] {10, 10, 20, 30});
    printRemoveDuplicates (new int[] {10, 10, 10, 20, 30});
    printRemoveDuplicates (new int[] {10, 20, 20, 30});
    printRemoveDuplicates (new int[] {10, 20, 20, 20, 30});
    printRemoveDuplicates (new int[] {10, 20, 30, 30});
    printRemoveDuplicates (new int[] {10, 20, 30, 30, 30});
    printRemoveDuplicates (new int[] {10, 10, 10, 10, 10, 10, 20, 20, 20, 30});
  }

  public static void main (String[] args) {
    testRemoveDuplicates ();
    //        args = new String[] { "data/tinyW.txt" };
    //        StdIn.fromFile ("data/tinyT.txt");
    //        int[] whitelist = new In (args[0]).readAllInts();
    //
    //        Arrays.sort (whitelist);
    //        whitelist = removeDuplicates (whitelist);
    //
    //        // read key; print if not in whitelist
    //        while (!StdIn.isEmpty ()) {
    //            int key = StdIn.readInt ();
    //            if (BinarySearch.rank (key, whitelist) == -1) StdOut.println (key);
    //        }
  }
}