fd

dingjikerbo · dingjikerbo · commit 5ffe35249784 · 2017-12-08T20:43:43.000+08:00
diff --git a/solution/src/main/java/com/inuker/solution/SearchForARange.java b/solution/src/main/java/com/inuker/solution/SearchForARange.java
@@ -7,46 +7,21 @@
 public class SearchForARange {
 
     public int[] searchRange(int[] nums, int target) {
-        int len = nums.length;
-
-        int left, right;
-
-        int[] result = new int[] { -1, -1 };
-
-        for (left = 0, right = len - 1; left < right; ) {
-            int mid = (left + right) / 2;
-
-            if (target > nums[mid]) {
-                left = mid + 1;
-            } else {
-                right = mid;
-            }
+        if (nums.length == 0) {
+            return new int[]{-1, -1};
         }
-
-        if (nums[left] != target) {
-            return result;
-        } else {
-            result[0] = left;
-        }
-
-        for (right = len - 1; left < right; ) {
-            int mid = (left + right) / 2 + 1;
-
-            if (target < nums[mid]) {
-                right = mid - 1;
-            } else {
-                left = mid;
-            }
-        }
-
-        result[1] = right;
-
-        return result;
+        return new int[] {
+                lowerBound(nums, target),
+                upperBound(nums, target)
+        };
     }
 
     /**
-    // 测试用例
-    // [5,7], [3,5], [5,5], [3,4], [6,7], [3,6], target = 5
+     * lowerBound和upperBound的TestCase
+     * [1,3],3
+     * [1,3],1
+     * [2,2],2
+     */
     public static int lowerBound(int[] nums, int target) {
         int left = 0, right = nums.length - 1;
 
@@ -78,5 +53,4 @@ public static int upperBound(int[] nums, int target) {
 
         return nums[right] == target ? right : -1;
     }
-     */
 }
diff --git a/test/src/main/java/com/inuker/test/Test2.java b/test/src/main/java/com/inuker/test/Test2.java
@@ -20,81 +20,45 @@
 
 public class Test2 {
 
-    public class AutocompleteSystem {
-
-        class TrieNode {
-            Map<Character, TrieNode> children;
-            Map<String, Integer> counts;
-            boolean isWord;
-            public TrieNode() {
-                children = new HashMap<Character, TrieNode>();
-                counts = new HashMap<String, Integer>();
-                isWord = false;
-            }
-        }
-
-        class Pair {
-            String s;
-            int c;
-            public Pair(String s, int c) {
-                this.s = s; this.c = c;
-            }
+    public int[] searchRange(int[] nums, int target) {
+        if (nums.length == 0) {
+            return new int[]{-1, -1};
         }
+        return new int[] {
+                lowerBound(nums, target),
+                upperBound(nums, target)
+        };
+    }
 
-        TrieNode root;
-        String prefix;
-
+    public static int lowerBound(int[] nums, int target) {
+        int left = 0, right = nums.length - 1;
 
-        public AutocompleteSystem(String[] sentences, int[] times) {
-            root = new TrieNode();
-            prefix = "";
+        while (left < right) {
+            int mid = left + ((right - left) >> 1);
 
-            for (int i = 0; i < sentences.length; i++) {
-                add(sentences[i], times[i]);
+            if (target > nums[mid]) {
+                left = mid + 1;
+            } else {
+                right = mid;
             }
         }
 
-        private void add(String s, int count) {
-            TrieNode curr = root;
-            for (char c : s.toCharArray()) {
-                TrieNode next = curr.children.get(c);
-                if (next == null) {
-                    next = new TrieNode();
-                    curr.children.put(c, next);
-                }
-                curr = next;
-                curr.counts.put(s, curr.counts.getOrDefault(s, 0) + count);
-            }
-            curr.isWord = true;
-        }
+        return nums[left] == target ? left : -1;
+    }
 
-        public List<String> input(char c) {
-            if (c == '#') {
-                add(prefix, 1);
-                prefix = "";
-                return new ArrayList<String>();
-            }
+    public static int upperBound(int[] nums, int target) {
+        int left = 0, right = nums.length - 1;
 
-            prefix = prefix + c;
-            TrieNode curr = root;
-            for (char cc : prefix.toCharArray()) {
-                TrieNode next = curr.children.get(cc);
-                if (next == null) {
-                    return new ArrayList<String>();
-                }
-                curr = next;
-            }
+        while (left < right) {
+            int mid = left + ((right - left) >> 1) + 1;
 
-            PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> (a.c == b.c ? a.s.compareTo(b.s) : b.c - a.c));
-            for (String s : curr.counts.keySet()) {
-                pq.add(new Pair(s, curr.counts.get(s)));
+            if (target < nums[mid]) {
+                right = mid - 1;
+            } else {
+                left = mid;
             }
-
-            List<String> res = new ArrayList<String>();
-            for (int i = 0; i < 3 && !pq.isEmpty(); i++) {
-                res.add(pq.poll().s);
-            }
-            return res;
         }
+
+        return nums[right] == target ? right : -1;
     }
 }
