object-C 解答算法:合并两个有序数组(leetCode-88)

合并两个有序数组(leetCode-88)

题目如下图:(也可以到leetCode上看完整题目,题号88)

首先搞懂,什么叫“非递减顺序”

非递减顺序,是指一个序列中的元素从前往后（或从左到右）保持不减少或相等。 这意味着序列中的元素可以保持相同的值，但不会突然减小。例如，序列1, 2, 3, 3, 4, 5就是非递减的，因为每个元素都大于或等于前一个元素。这与递增顺序不同，递增顺序要求每个元素都严格大于前一个元素。在编程和算法中，非递减顺序有时用于合并或处理数组，确保操作后的数组仍然保持这种顺序.

解题方法一:

明白了非递减顺序之后,第一想法其实就是合并数组后,将数组里的整数进行排序就行;

不过这里的合并函数是有说法的,因为题干的“注意”说了,nums1 的初始长度为m+n,前m个才是需要合并的元素,所以合并的时候,我们不需要管 nums1 数组里 index=m之后的元素. 同样的,我们也不需要管nums2数组里 index=n之后的元素.所以合并的逻辑应该为;

即: (⚠️:我这里稍微改了示例1中的数字,因为示例1中的m和n 都为3, 会容易让人误解,实际上只要nums的长度m+n,那么n随意等于多少,可以是1,2,3,4,5……)

    int m = 3;
    int n = 2;
    NSMutableArray * array1 = [[NSMutableArray alloc]initWithObjects:@"1",@"2",@"3",@"0",@"0", nil];
    NSMutableArray * array2 = [[NSMutableArray alloc]initWithObjects:@"2",@"5",@"9",@"6", nil];
    for (int i = 0; i < n; i ++)
    {
        array1[m+i] = array2[i];
    }
    
    //接下来对array1进行排序,有冒泡排序,选择排序,插入排序等等,可以参考我主页的排序介绍

排序的方法看我的其他文章:

冒泡排序:CSDN

选择排序:CSDN

解题方法二:

直接比较两个数组的每个元素的大小,把最小的放在前面,依次排列 添加到一个新的数组tempArray;如果nums1里 已经添加了m个元素,则说明array1里的其他元素不可以再添加,则后面添加的都是nums2的元素,同理可得,如果nums2已经添加了n个元素,则后面添加的都是nums1的元素.

最后得到的tempArray即是合并后的“非递减顺序”排列,但是题干要求最终的结果要体现在nums1.所以再把tempArray 的元素赋值给nums1元素:

代码如下:

- (void)twoArray1:(NSMutableArray *)array1 Array2:(NSMutableArray *)array2 M:(int)m N:(int)n
{
    NSMutableArray * tempArray = [[NSMutableArray alloc]init];
    int k = n+m;
    for (int index = 0 ,arrayIndex1 = 0, arrayIndex2 = 0; index < k; index++) 
    {
        if (arrayIndex1 >= m)
        {
            //array1数组已经取完了,剩下的完全取array2数组即可
            tempArray[index] = array2[arrayIndex2];
            arrayIndex2 ++;
        }else if (arrayIndex2 >= n){ //array2数组已经取完了,剩下的完全取array1数组即可
            
            tempArray[index] = array1[arrayIndex1];
            arrayIndex1 ++;
            
        }else if ([array1[arrayIndex1] intValue] < [array2[arrayIndex2] intValue]){
            //array1数组的元素值小于array2,则取array1数组的值
            tempArray[index] = array1[arrayIndex1];
            arrayIndex1 ++;
        }else{ //array2数组的元素值小于array1,则取array2数组的值
            tempArray[index] = array2[arrayIndex2];
            arrayIndex2 ++;
        }
    }
    
    //最后把tempArray的元素赋值到array1上
    for (int i = 0; i < k; i ++)
    {
        array1[i] = tempArray[i];
    }
    
}