双指针（88.合并两个有序数组）
/**
题目
【双指针（88.合并两个有序数组）】给你两个有序整数数组 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]
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[i] <= 109
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
测试代码
var nums1 = [1,2,3,0,0,0]
merge(&nums1, 3, [2,5,6], 3)
print(nums1)
笔记
第一种思路 把第二个数组里的数组放到第一个数组里然后排序
第二种思路 创建一个新数组,每次从原来的两个数组里从前往后取,找到最小的那个元素放进新数组里
第三种思路 不开启新空间,就在第一个数组里进行处理,从后往前取最大值
下面重点讲讲第三种思路,应该算是三指针吧
第一个index1 指向 m-1,即第一个数组的有效数据末端
第一个index2 指向 n-1,即第二个数组的末端
第三个indexCur 指向 m + n - 1, 即包含无效数据的第一个数组的末端
然后从后往前遍历无效数据的第一个数组, 即 第三个指针indexCur -= 1
在每一个位置都去比较 index1 和 index2 的元素
取出较大的一个放到 indexCur
对应的 index1 或者 index2 -= 1 即可
注意这种思路处理的时候,如果取的是 index1, 要和 indexCur 进行数据交换
代码地址
https://github.com/zmfflying/ZMathCode
*/
解题代码
import Foundationfunc merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
//记录第一个数组的有效数据末端索引
var index1 = m - 1
//第二个数组的末端索引
var index2 = n - 1//记录正在处理的索引
var indexCur = m + n - 1//从尾端开始处理
while indexCur >= 0 {
//找出当前未处理的两段数据的值
let numIndex1 = index1 < 0 ? Int.min : nums1[index1]
let numIndex2 = index2 < 0 ? Int.min : nums2[index2]//取出最大值放在尾端
//同时对应索引 -= 1
if numIndex1 > numIndex2 {
//如果是第一段数据要注意交换数据
if nums1[indexCur] != numIndex1 {
nums1[index1] = nums1[indexCur]
nums1[indexCur] = numIndex1
}
index1 -= 1
} else {
nums1[indexCur] = numIndex2
index2 -= 1
}
indexCur -= 1
}
}//这种和上面的思路一样,优化后只用处理 n 次就行了, 但是没有上面好理解
//func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
//var index1 = m - 1
//var index2 = n - 1
//var indexCur = m + n - 1
//
//while index2 >= 0 {
//if index1 >= 0 && nums1[index1] > nums2[index2] {
//nums1[indexCur] = nums1[index1]
//index1 -= 1
//} else {
//nums1[indexCur] = nums2[index2]
//index2 -= 1
//}
//indexCur -= 1
//}
//}推荐阅读
- 爱琐搭配（喜欢复古、冷淡，像这种双环设计的气质耳环）
- 唐嫣可真会穿，西装搭牛仔裤都能穿出高级感，一双大长腿太抢镜
- 宝贝你总是给我惊喜
- 诗‖失德
- 友人分享双鹅图片，为写俚句
- 双烧眼
- echart|echart 双轴图开发
- V-learn小西妈双语工程2017年03期144号谢思岩Carlos2017.10.21-10.22
- 你有一双发现美的眼睛吗（）
- ROOM1