Jamzen的技术博客
0%

LeetCode.合并两个有序数组

发表于 分类于 Valine：

给你两个有序整数数组nums1和nums2，请你将nums2合并到nums1中，使nums1成为一个有序数组。初始化nums1和nums2的元素数量分别为m和n。你可以假设nums1有足够的空间(空间大小大于或等于m+n)来保存nums2中的元素。

  • 示例1：
    输入：
    nums1 = [1,2,3,0,0,0], m = 3
    nums2 = [2,5,6], n = 3
    输出：[ 1, 2, 2, 3, 5, 6 ]

解法：

1
2
3
4
5
6
7
8
9
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
object MergeTwoSortedArray {
     def main(args: Array[String]): Unit = {
          val arr1 = Array(1, 2, 3, 0, 0, 0)
          val arr2 = Array(2, 5, 6)
          merge(arr1, 3, arr2, 3)
          println(java.util.Arrays.toString(arr1))
     }

     def merge(nums1: Array[Int], m: Int, nums2: Array[Int], n: Int): Unit = {
          var i = m + n - 1
          var l = m - 1
          var r = n - 1
          while (l >= 0 && r >= 0) {
               if (nums1(l) > nums2(r)) {
                    nums1(i) = nums1(l)
                    l -= 1
               } else {
                    nums1(i) = nums2(r)
                    r -= 1
               }
               i -= 1
          }

          while (l >= 0) {
               nums1(i) = nums1(l)
               l -= 1
               i -= 1
          }

          while (r >= 0) {
               nums1(i) = nums2(r)
               r -= 1
               i -= 1
          }
     }
}