001// Exercise 1.1.28 002package algs11; 003import stdlib.*; 004import java.util.Arrays; 005 006/* 007 1.1.28 Remove duplicates. 008 Modify the test client in BinarySearch to remove any duplicate keys in the whitelist after the sort. 009 010 Hint: For this problem, you will need to create a second array that is 011 smaller than the original whitelist. You need to go through the 012 original whitelist twice. The first time, you need to determine the number 013 of unique items in the whitelist; use this as the size of the second array, 014 which you create. The second time, copy the unique items to the new 015 array. 016 */ 017public class MyBinarySearchRemoveDuplicates { 018 019 // precondition: array a[] is sorted 020 public static int rank (int key, int[] a) { 021 int lo = 0; 022 int hi = a.length - 1; 023 while (lo <= hi) { 024 // key is in a[lo..hi] or not present. 025 int mid = lo + (hi - lo) / 2; 026 if (key < a[mid]) hi = mid - 1; 027 else if (key > a[mid]) lo = mid + 1; 028 else return mid; 029 } 030 return -1; 031 } 032 033 // precondition: array a[] is sorted 034 public static int[] removeDuplicates (int[] a) { 035 int N = a.length; 036 if (N < 1) return a; 037 038 // determine number of unique elements 039 // TODO 040 041 // copy from a to new array 042 // TODO 043 return null; 044 } 045 046 public static void printRemoveDuplicates (int[] a) { 047 //StdOut.println (Arrays.toString (a)); 048 StdOut.println (Arrays.toString (removeDuplicates (a))); 049 } 050 051 public static void testRemoveDuplicates () { 052 printRemoveDuplicates (new int[] {}); 053 printRemoveDuplicates (new int[] {10}); 054 printRemoveDuplicates (new int[] {10, 10}); 055 printRemoveDuplicates (new int[] {10, 20}); 056 printRemoveDuplicates (new int[] {10, 10, 20, 30}); 057 printRemoveDuplicates (new int[] {10, 10, 10, 20, 30}); 058 printRemoveDuplicates (new int[] {10, 20, 20, 30}); 059 printRemoveDuplicates (new int[] {10, 20, 20, 20, 30}); 060 printRemoveDuplicates (new int[] {10, 20, 30, 30}); 061 printRemoveDuplicates (new int[] {10, 20, 30, 30, 30}); 062 printRemoveDuplicates (new int[] {10, 10, 10, 10, 10, 10, 20, 20, 20, 30}); 063 } 064 065 public static void main (String[] args) { 066 testRemoveDuplicates (); 067 // args = new String[] { "data/tinyW.txt" }; 068 // StdIn.fromFile ("data/tinyT.txt"); 069 // int[] whitelist = new In (args[0]).readAllInts(); 070 // 071 // Arrays.sort (whitelist); 072 // whitelist = removeDuplicates (whitelist); 073 // 074 // // read key; print if not in whitelist 075 // while (!StdIn.isEmpty ()) { 076 // int key = StdIn.readInt (); 077 // if (BinarySearch.rank (key, whitelist) == -1) StdOut.println (key); 078 // } 079 } 080}