能力有限，水平一般，如果有错误，请不吝赐教。😁
给你两个有序整数数组 nums1 和 nums2，请你将nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化nums1 和nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
OC语言实现
方式1：
- (void)merge:(NSArray *)nums1 m:(int)m nums2:(NSArray *)nums2 n:(int)n {
/**
* 原理数这样的：
* 1、创建一个大小为m+n的数组。这样我们就得到了三个数组，source,nums1,nums2,
* 2、创建三个下标（指针），分别指向source/nums1/nums2的首元素。
* 3、创建循环，目的是取出nums1/nums2数组中较小的数字，放入新的数组当中，
* 并将对应的下标加1（p++并且(p1++或者p2++)），一直到打破循环（p1 == m 或者 p2 == n）
* 4、循环完成后，必然出现的结果就是：p1 < m 或者 p2 < n，两种情况必然出现一种。
* p1 < m，nums1中存在较大的元素，因此num1中存在未被添加到source的元素；
* p2 < m，nums2中存在较大的元素，因此num2中存在未被添加到source的元素；
* 我们只需要，直接取出（或者遍历）loc:p1/p2 length:m-p1/n-p2 的元素即可。
*/
// 得到最终排序结果的数组
NSMutableArray *source = [NSMutableArray arrayWithCapacity:(m+n)];
int p = 0; // 指向souce数组的元素的下标
int p1 = 0; // 指向nums1数组的元素的下标
int p2 = 0; // 指向nums2数组的元素的下标
while (p1 < m && p2 < n) {
if ([nums1[p1] intValue] <= [nums2[p2] intValue]) {
// 取出nums1中较小的元素
source[p] = nums1[p1];
// nums1下标（指针）自增
p1++;
}
else {
// 取出nums2中较小的元素
source[p] = nums2[p2];
// nums2下标（指针）自增
p2++;
}
// source下标（指针）自增
p++;
}
if (p1 < m) { // nums1中剩余元素
// 直接取
[source addObjectsFromArray:[nums1 subarrayWithRange:NSMakeRange(p1, m-p1)]];
// // 遍历
// for (int i = p1; i < m; i++) {
// source[p] = nums1[i];
// p++;
// }
}
if (p2 < n) { // nums2中剩余元素
[source addObjectsFromArray:[nums2 subarrayWithRange:NSMakeRange(p2, n-p2)]];
// // 遍历
// for (int i = p2; i < n; i++) {
// source[p] = nums2[i];
// p++;
// }
}
NSLog(@"source == %@",[source componentsJoinedByString:@","]);
}
方式2：
- (void)merge1:(NSMutableArray *)nums1 m:(int)m nums2:(NSArray *)nums2 n:(int)n {
/**
* 原理数这样的：
* 1、创建三个下标（指针），分别指向nums1的最后一个元素、nums1的最后一个有效元素 和 nums2的最后一个元素。
* num1的理论长度是m+n,必然有后n位元素是无效的元素，这里暂时用0来标识。
* 这里要注意的是nums1需要时可变数组，否则不能修改元素。
* 2、创建循环，目的是取出nums1[p1] 和 nums2[p2] 中较大的数字，放入nums1[p]上，
* 并将对应的下标减1（p--并且p1--或者p2--），一直到打破循环（p1 < 0 或者 p2 < 0）
* 3、循环完成后，必然出现的结果就是：p1 < 0 并且 p2 >= 0 或者 p2 < 0 并且 p1 >= 0，两种情况必然出现一种。
* p1 >= 0，nums1中存在较小的元素，因此num1中存在未被循环遍历到的元素；
* p2 >= 0，nums2中存在较小的元素，因此num2中存在未被循环遍历到的元素；
* 我们只需要，倒叙遍历p1...0 或者 p2...0 出元素，并赋值到nums[p](p--)中即可。
*/
// n == 0，即nums2无元素，直接返回nums1中的有效元素（m个）
if (n == 0) {
NSLog(@"source == %@",[[nums1 subarrayWithRange:NSMakeRange(0, m)] componentsJoinedByString:@","]);
return;
}
int p = m+n-1; // 指向nums1的最后一个元素的下标
int p1 = m-1; // 指向nums1的最后一个有效元素的下标
int p2 = n-1; // 指向nums2的最后一个元素的下标
while (p1 >= 0 && p2 >= 0) {
if ([nums1[p1] intValue] < [nums2[p2] intValue]) {
// 取出较大的元素
nums1[p] = nums2[p2];
// 下标前移
p2--;
}
else {
// 取出较大的元素
nums1[p] = nums1[p1];
// 下标前移
p1--;
}
// 下标前移
p--;
}
if (p1 >= 0) { // nums1中剩余元素
// 倒叙遍历
for (int i = p1; i >= 0; i--) {
nums1[p] = nums1[i];
p--;
}
}
if (p2 >= 0) { // nums2中剩余元素
// 倒叙遍历
for (int i = p2; i >= 0; i--) {
nums1[p] = nums2[i];
p--;
}
}
NSLog(@"source == %@",[nums1 componentsJoinedByString:@","]);
}
swift语言实现
方式1：
func merge(nums1:[Int],m:Int,nums2:[Int],n:Int) -> Void {
var source: [Int] = Array.init(repeating: 0, count: m+n)
var p = 0
var p1 = 0
var p2 = 0
while p1 < m && p2 < n {
if nums1[p1] < nums2[p2] {
source[p] = nums1[p1]
p1 += 1
}
else {
source[p] = nums2[p2]
p2 += 1
}
p += 1
}
if p1 < m {
let range = p..<(p+m-p1)
let range1 = p1..<m
source.replaceSubrange(range, with: nums1[range1])
}
if p2 < n {
let range = p..<(p+n-p2)
let range2 = p2..<n
source.replaceSubrange(range, with: nums2[range2])
}
print("source == ",source)
}
方式2：
func merge1(nums1: inout [Int],m:Int,nums2:[Int],n:Int) -> Void {
if m == 0 {
// 空数组
return
}
if n == 0 {
let range = 0...m
print("source == ",nums1[range])
return;
}
var p = m+n-1
var p1 = m-1
var p2 = n-1
while p1 >= 0 && p2 >= 0 {
if nums1[p1] < nums2[p2] {
nums1[p] = nums2[p2]
p2 -= 1
}
else {
nums1[p] = nums1[p1]
p1 -= 1
}
p -= 1
}
if p1 >= 0 {
for index in 0...p1 {
nums1[p] = nums1[p1-index]
p -= 1
}
}
if p2 >= 0 {
for index in 0...p2 {
nums1[p] = nums2[p2-index]
p -= 1
}
}
print("source == ",nums1)
}
网友评论