[Swift]LeetCode88.合并两个有序数组|MergeSortedArray

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9697984.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

8ms

 1 class Solution {
 2     func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
 3         var index1 = 0
 4         var index2 = 0
 5         
 6         while index2 < n {
 7             if nums1[index1] > nums2[index2] || index1-index2 >= m {
 8                 nums1.insert(nums2[index2], at: index1)
 9                 index1 += 1
10                 index2 += 1
11             } else if nums1[index1] <= nums2[index2] {
12                 index1 += 1
13             }
14         }
15     }
16 }

12ms

 1 /**
 2  * 思路：从尾部开始合并，避免覆盖
 3  * 时间复杂度：O(n)，空间复杂度：O(1)
 4  */
 5 class Solution {
 6     func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
 7         var i = m - 1, j = n - 1
 8         
 9         while i >= 0 || j >= 0 {
10             if j < 0 || (i >= 0 && nums1[i] > nums2[j]) {
11                 nums1[i + j + 1] = nums1[i]
12                 i -= 1
13             } else {
14                 nums1[i + j + 1] = nums2[j]
15                 j -= 1
16             }
17         }
18     }
19 }

16ms

 1 class Solution {
 2     func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
 3             var i = m - 1, j = n - 1
 4     while i + j + 1 >= 0 && j != -1 {
 5         if i >= 0 && nums1[i] >= nums2[j] {
 6             nums1[i + j + 1] = nums1[i]
 7             i = i - 1
 8         } else {
 9             nums1[i + j + 1] = nums2[j]
10             j = j - 1
11         }
12     }
13     }
14 }

16ms

 1 class Solution {
 2     func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
 3         var i = 0, j = 0
 4         
 5         while j < n && i < nums1.count {
 6             if (nums1[i] < nums2[j] && i < m + j) {
 7                 i += 1
 8             } else {
 9                 nums1.insert(nums2[j], at: i)
10                 i += 1
11                 j += 1
12             }
13         }
14         if nums1.count > n + m {
15             nums1.removeLast(nums1.count - n - m)
16         }
17     }
18 }

20ms

1 class Solution {
2     func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
3         
4         for i in m..<m+n {
5             nums1[i] = nums2[i-m]
6         }
7         nums1 = nums1.sorted()
8     }
9 }

20ms

 1 class Solution {
 2     func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
 3         guard m > 0 else {
 4             nums1 = nums2
 5             return
 6         }
 7         
 8         guard n > 0 else {
 9             return
10         }
11         
12         var i = 0
13         var j = 0
14         
15         var mergedNums = Array(nums1[..<m])
16         print("MergedNums: \(mergedNums)")
17         
18         while i < mergedNums.count && j < n {
19             if nums2[j] <= mergedNums[i] {
20                 mergedNums.insert(nums2[j], at: i)
21                 j += 1
22             } else {
23                 i += 1
24             }
25         }
26         
27         if j < n {
28             mergedNums += nums2[j..<n]
29         }
30         
31         nums1 = mergedNums
32     }
33 }

32ms

 1 class Solution {
 2     func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
 3         var j = m - 1
 4         var i = n - 1
 5         var k = m + n - 1
 6         
 7         while (i >= 0) {
 8             if (j >= 0 && (nums1[j] > nums2[i])) {
 9                 nums1[k] = nums1[j]
10                  j -= 1 
11             } else {
12                 nums1[k] = nums2[i]
13                 i -= 1
14             }
15               k -= 1
16         }
17     }
18 }

36ms

 1 class Solution {
 2     func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
 3         var sArr = ArraySlice<Int>()
 4         if m != 0 && m<=nums1.count {
 5            sArr = nums1[0...(m-1)]
 6         }
 7         if n != 0 && n <= nums2.count  {
 8             sArr.append(contentsOf: nums2[0...(n-1)])
 9         }
10         nums1.removeAll()
11         nums1.append(contentsOf: sArr)
12         nums1.sort { (x, y) -> Bool in
13             return x < y
14         }  
15     }
16 }

40ms

 1 class Solution {
 2     func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
 3         
 4         for i in 0..<nums2.count{
 5         
 6             nums1[m+i]=nums2[i]
 7         }
 8         
 9         
10         nums1 = quickSort(data:nums1)
11         
12     }
13    func quickSort(data:[Int])->[Int]{
14         if data.count<=1 {
15             return data
16         }
17         
18         var left:[Int] = []
19         var right:[Int] = []
20         let pivot:Int = data[data.count-1]
21         for index in 0..<data.count-1 {
22             if data[index] < pivot {
23                 left.append(data[index])
24             }else{
25                 right.append(data[index])
26             }
27         }
28         
29         var result = quickSort(data: left)
30         result.append(pivot)
31         let rightResult = quickSort(data: right)
32         result.append(contentsOf: rightResult)
33         return result
34     }
35 }