optimize algorithm sand save space for 1200

fishercoder1534 · fishercoder1534 · commit 8221b4969f7f · 2019-11-23T06:50:10.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_1200.java b/src/main/java/com/fishercoder/solutions/_1200.java
@@ -3,7 +3,6 @@
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
-import java.util.TreeMap;
 
 /**
  * 1200. Minimum Absolute Difference
@@ -39,20 +38,20 @@ public static class Solution1 {
          * */
         public List<List<Integer>> minimumAbsDifference(int[] arr) {
             Arrays.sort(arr);
-            TreeMap<Integer, List<List<Integer>>> map = new TreeMap<>();
-            for (int i = 0; i < arr.length - 1; i++) {
+            int minimumDiff = arr[1] - arr[0];
+            List result = new ArrayList();
+            result.add(Arrays.asList(arr[0], arr[1]));
+            for (int i = 1; i < arr.length - 1; i++) {
                 int diff = arr[i + 1] - arr[i];
-                if (map.containsKey(diff)) {
-                    List list = map.get(diff);
-                    list.add(Arrays.asList(arr[i], arr[i + 1]));
-                    map.put(diff, list);
-                } else {
-                    List list = new ArrayList<>();
-                    list.add(Arrays.asList(arr[i], arr[i + 1]));
-                    map.put(diff, list);
+                if (minimumDiff == diff) {
+                    result.add(Arrays.asList(arr[i], arr[i+1]));
+                } else if (minimumDiff > diff) {
+                    minimumDiff = diff;
+                    result = new ArrayList();
+                    result.add(Arrays.asList(arr[i], arr[i+1]));
                 }
             }
-            return map.firstEntry().getValue();
+            return result;
         }
     }
 }
diff --git a/src/test/java/com/fishercoder/_1200Test.java b/src/test/java/com/fishercoder/_1200Test.java
@@ -30,4 +30,12 @@ public void test1() {
         assertEquals(expected, solution1.minimumAbsDifference(arr));
     }
 
+    @Test
+    public void test2() {
+        arr = new int[]{40, 11, 26, 27, -20};
+        expected = new ArrayList<>();
+        expected.add(Arrays.asList(26, 27));
+        assertEquals(expected, solution1.minimumAbsDifference(arr));
+    }
+
 }

Original file line number	Diff line number	Diff line change
`@@ -30,4 +30,12 @@ public void test1() {`
`30`	`30`	`assertEquals(expected, solution1.minimumAbsDifference(arr));`
`31`	`31`	`}`
`32`	`32`
	`33`	`+ @Test`
	`34`	`+ public void test2() {`
	`35`	`+ arr = new int[]{40, 11, 26, 27, -20};`
	`36`	`+ expected = new ArrayList<>();`
	`37`	`+ expected.add(Arrays.asList(26, 27));`
	`38`	`+ assertEquals(expected, solution1.minimumAbsDifference(arr));`
	`39`	`+ }`
	`40`	`+`
`33`	`41`	`}`