能力有限零渐，水平一般，如果有錯誤，請不吝賜教淌哟。??
給你兩個有序整數(shù)數(shù)組 nums1 和 nums2迹卢，請你將nums2 合并到 nums1 中，使 nums1 成為一個有序數(shù)組徒仓。
初始化nums1 和nums2 的元素數(shù)量分別為 m 和 n 婶希。你可以假設 nums1 的空間大小等于 m + n，這樣它就有足夠的空間保存來自 nums2 的元素蓬衡。
OC語言實現(xiàn)
方式1：
- (void)merge:(NSArray *)nums1 m:(int)m nums2:(NSArray *)nums2 n:(int)n {
/**
* 原理數(shù)這樣的：
* 1喻杈、創(chuàng)建一個大小為m+n的數(shù)組。這樣我們就得到了三個數(shù)組狰晚，source,nums1,nums2,
* 2筒饰、創(chuàng)建三個下標（指針），分別指向source/nums1/nums2的首元素壁晒。
* 3瓷们、創(chuàng)建循環(huán)，目的是取出nums1/nums2數(shù)組中較小的數(shù)字秒咐，放入新的數(shù)組當中谬晕，
* 并將對應的下標加1（p++并且(p1++或者p2++)），一直到打破循環(huán)（p1 == m 或者 p2 == n）
* 4携取、循環(huán)完成后攒钳，必然出現(xiàn)的結果就是：p1 < m 或者 p2 < n，兩種情況必然出現(xiàn)一種雷滋。
* p1 < m不撑，nums1中存在較大的元素，因此num1中存在未被添加到source的元素晤斩；
* p2 < m焕檬，nums2中存在較大的元素，因此num2中存在未被添加到source的元素澳泵；
* 我們只需要实愚，直接取出（或者遍歷）loc:p1/p2 length:m-p1/n-p2 的元素即可。
*/
// 得到最終排序結果的數(shù)組
NSMutableArray *source = [NSMutableArray arrayWithCapacity:(m+n)];
int p = 0; // 指向souce數(shù)組的元素的下標
int p1 = 0; // 指向nums1數(shù)組的元素的下標
int p2 = 0; // 指向nums2數(shù)組的元素的下標
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 {
/**
* 原理數(shù)這樣的：
* 1兔辅、創(chuàng)建三個下標（指針）腊敲，分別指向nums1的最后一個元素、nums1的最后一個有效元素 和 nums2的最后一個元素幢妄。
* num1的理論長度是m+n,必然有后n位元素是無效的元素兔仰，這里暫時用0來標識茫负。
* 這里要注意的是nums1需要時可變數(shù)組蕉鸳，否則不能修改元素。
* 2、創(chuàng)建循環(huán)潮尝，目的是取出nums1[p1] 和 nums2[p2] 中較大的數(shù)字榕吼，放入nums1[p]上，
* 并將對應的下標減1（p--并且p1--或者p2--）勉失，一直到打破循環(huán)（p1 < 0 或者 p2 < 0）
* 3羹蚣、循環(huán)完成后，必然出現(xiàn)的結果就是：p1 < 0 并且 p2 >= 0 或者 p2 < 0 并且 p1 >= 0乱凿，兩種情況必然出現(xiàn)一種顽素。
* p1 >= 0，nums1中存在較小的元素徒蟆，因此num1中存在未被循環(huán)遍歷到的元素胁出；
* p2 >= 0，nums2中存在較小的元素段审，因此num2中存在未被循環(huán)遍歷到的元素全蝶；
* 我們只需要，倒敘遍歷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語言實現(xiàn)
方式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 {
// 空數(shù)組
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)
}
