merge sorted array (examplehub#143)

realDuYuanChao · github-actions · web-flow · commit ebd6c39c4e9e · 2021-08-04T08:30:57.000+08:00
* add test

* merge sorted array

* Formatted with Google Java Formatter

Co-authored-by: github-actions &lt;${GITHUB_ACTOR}@users.noreply.github.com&gt;
diff --git a/src/main/java/com/examplehub/leetcode/easy/MergeSortedArray.java b/src/main/java/com/examplehub/leetcode/easy/MergeSortedArray.java
@@ -0,0 +1,68 @@
+package com.examplehub.leetcode.easy;
+
+import java.util.Arrays;
+
+/** https://leetcode.com/problems/merge-sorted-array/ */
+public class MergeSortedArray {
+  public static void solution1(int[] nums1, int m, int[] nums2, int n) {
+    int[] temp = new int[m + n];
+    int firstIndex = 0;
+    int secondIndex = 0;
+    int index = 0;
+    while (firstIndex < m && secondIndex < n) {
+      if (nums1[firstIndex] <= nums2[secondIndex]) {
+        temp[index++] = nums1[firstIndex++];
+      } else {
+        temp[index++] = nums2[secondIndex++];
+      }
+    }
+    while (firstIndex < m) {
+      temp[index++] = nums1[firstIndex++];
+    }
+    while (secondIndex < n) {
+      temp[index++] = nums2[secondIndex++];
+    }
+    System.arraycopy(temp, 0, nums1, 0, m + n);
+  }
+
+  public static void solution2(int[] nums1, int m, int[] nums2, int n) {
+    System.arraycopy(nums2, 0, nums1, m, n);
+    Arrays.sort(nums1);
+  }
+
+  public static void solution3(int[] nums1, int m, int[] nums2, int n) {
+    int[] sorted = new int[m + n];
+    int firstIndex = 0;
+    int secondIndex = 0;
+    int index = 0;
+    while (firstIndex < m || secondIndex < n) {
+      if (firstIndex == m) {
+        sorted[index++] = nums2[secondIndex++];
+      } else if (secondIndex == n) {
+        sorted[index++] = nums1[firstIndex++];
+      } else if (nums1[firstIndex] <= nums2[secondIndex]) {
+        sorted[index++] = nums1[firstIndex++];
+      } else {
+        sorted[index++] = nums2[secondIndex++];
+      }
+    }
+    System.arraycopy(sorted, 0, nums1, 0, m + n);
+  }
+
+  public static void solution4(int[] nums1, int m, int[] nums2, int n) {
+    int firstIndex = m - 1;
+    int secondIndex = n - 1;
+    int index = m + n - 1;
+    while (firstIndex >= 0 || secondIndex >= 0) {
+      if (firstIndex == -1) {
+        nums1[index--] = nums2[secondIndex--];
+      } else if (secondIndex == -1) {
+        nums1[index--] = nums1[firstIndex--];
+      } else if (nums1[firstIndex] >= nums2[secondIndex]) {
+        nums1[index--] = nums1[firstIndex--];
+      } else {
+        nums1[index--] = nums2[secondIndex--];
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/examplehub/leetcode/easy/MergeSortedArrayTest.java b/src/test/java/com/examplehub/leetcode/easy/MergeSortedArrayTest.java
@@ -0,0 +1,80 @@
+package com.examplehub.leetcode.easy;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import java.util.Arrays;
+import org.junit.jupiter.api.Test;
+
+class MergeSortedArrayTest {
+  @Test
+  void testSolution1() {
+    int[] nums1 = {1, 2, 3, 0, 0, 0};
+    int[] nums2 = {2, 5, 6};
+    MergeSortedArray.solution1(nums1, 3, nums2, 3);
+    assertEquals("[1, 2, 2, 3, 5, 6]", Arrays.toString(nums1));
+
+    nums1 = new int[] {1};
+    nums2 = new int[] {};
+    MergeSortedArray.solution1(nums1, 1, nums2, 0);
+    assertEquals("[1]", Arrays.toString(nums1));
+
+    nums1 = new int[1];
+    nums2 = new int[] {1};
+    MergeSortedArray.solution1(nums1, 0, nums2, 1);
+    assertEquals("[1]", Arrays.toString(nums1));
+  }
+
+  @Test
+  void testSolution2() {
+    int[] nums1 = {1, 2, 3, 0, 0, 0};
+    int[] nums2 = {2, 5, 6};
+    MergeSortedArray.solution2(nums1, 3, nums2, 3);
+    assertEquals("[1, 2, 2, 3, 5, 6]", Arrays.toString(nums1));
+
+    nums1 = new int[] {1};
+    nums2 = new int[] {};
+    MergeSortedArray.solution2(nums1, 1, nums2, 0);
+    assertEquals("[1]", Arrays.toString(nums1));
+
+    nums1 = new int[1];
+    nums2 = new int[] {1};
+    MergeSortedArray.solution2(nums1, 0, nums2, 1);
+    assertEquals("[1]", Arrays.toString(nums1));
+  }
+
+  @Test
+  void testSolution3() {
+    int[] nums1 = {1, 2, 3, 0, 0, 0};
+    int[] nums2 = {2, 5, 6};
+    MergeSortedArray.solution3(nums1, 3, nums2, 3);
+    assertEquals("[1, 2, 2, 3, 5, 6]", Arrays.toString(nums1));
+
+    nums1 = new int[] {1};
+    nums2 = new int[] {};
+    MergeSortedArray.solution3(nums1, 1, nums2, 0);
+    assertEquals("[1]", Arrays.toString(nums1));
+
+    nums1 = new int[1];
+    nums2 = new int[] {1};
+    MergeSortedArray.solution3(nums1, 0, nums2, 1);
+    assertEquals("[1]", Arrays.toString(nums1));
+  }
+
+  @Test
+  void testSolution4() {
+    int[] nums1 = {1, 2, 3, 0, 0, 0};
+    int[] nums2 = {2, 5, 6};
+    MergeSortedArray.solution4(nums1, 3, nums2, 3);
+    assertEquals("[1, 2, 2, 3, 5, 6]", Arrays.toString(nums1));
+
+    nums1 = new int[] {1};
+    nums2 = new int[] {};
+    MergeSortedArray.solution4(nums1, 1, nums2, 0);
+    assertEquals("[1]", Arrays.toString(nums1));
+
+    nums1 = new int[1];
+    nums2 = new int[] {1};
+    MergeSortedArray.solution4(nums1, 0, nums2, 1);
+    assertEquals("[1]", Arrays.toString(nums1));
+  }
+}
diff --git a/src/test/java/com/examplehub/sorts/QuickSortEasyPartitionTest.java b/src/test/java/com/examplehub/sorts/QuickSortEasyPartitionTest.java
@@ -21,6 +21,10 @@ void testQuickSort() {
     int[] ints = RandomUtils.randomInts(-50, 50, 100);
     sort.sort(ints);
     assertTrue(SortUtils.isSorted(ints));
+
+    ints = new int[] {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
+    sort.sort(ints);
+    assertTrue(SortUtils.isSorted(ints));
   }
 
   @Test
diff --git a/src/test/java/com/examplehub/sorts/QuickSortTest.java b/src/test/java/com/examplehub/sorts/QuickSortTest.java
@@ -22,6 +22,10 @@ void testQuickSort() {
     int[] ints = RandomUtils.randomInts(-50, 50, 100);
     sort.sort(ints);
     assertTrue(SortUtils.isSorted(ints));
+
+    ints = new int[] {0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
+    sort.sort(ints);
+    assertTrue(SortUtils.isSorted(ints));
   }
 
   @Test
