iphone - NSArray方法算法逻辑

Question

我是 Objective-C 语言的新手，在面试中被问到一个我无法回答的问题。

我尝试了很多方法和逻辑都没有成功。在这里寻找答案:

问题是:

 - (NSArray *)reorderTheArraysAndMergeThemInDescendingOrder:(NSArray *)firstArray and:(NSArray *)secondArray

参数中提供的两个数组都已按升序排序。

我的任务是提供一个数组作为返回变量，它将包含 firstArray 和 secondArray 的所有唯一元素，并将它们按降序排列。我不被允许使用 Objective-C 的内置排序功能(自从我进入这个领域以来，我就是这样做的)。我的变量可能只是基元(结果当然是一个整数数组。)。

我是整个编程领域的新手，非常感谢这里的好答案。

朱鹤

Answer 1

由于提供的数组是按升序排序的，所以这个问题与 Mergesort 的经典算法非常相关。 (没听过的可以看看，经典之作)。

由于您的数组仅包含原始数据类型，因此可以使用 < 来比较它们

你感兴趣的代码应该是这样的

- (NSArray *)reorderAndMergeReverse:(NSArray *)array1 and:(NSArray *)array2{

    NSMutableArray *result = [NSMUtableArray array];

     int i = array1.count-1;
     int j = array2.count-1;

     while (result.count < array1.count+array2.count){

        if ([array1 objectAtIndex:i] > [array2 objectAtIndex:j]){
             [result addObject:[array1 objectAtIndex:i]];
             i--:
        } else {
            [result addObject:[array2 objectAtIndex:j]];
             j--:
        }

     }
     return result;
}

我不确定您是否要删除重复项，您的问题不是很清楚，您介意告诉我是否要删除重复项以便我改进我的代码吗？
编辑:无论如何都做了:因为你的数组是排序的，重复的只是彼此相邻，所以可能很容易不首先添加它们；

- (NSArray *)reorderAndMergeReverse:(NSArray *)array1 and:(NSArray *)array2{

    NSMutableArray *result = [NSMUtableArray array];

     int i = array1.count-1;
     int j = array2.count-1;
     int k = 0;

     while (i>=0 || j>=0){

        if ([array1 objectAtIndex:i] > [array2 objectAtIndex:j]){
             if ([array1 objectAtIndex:i] != [result objectAtIndex:k]){
                 [result addObject:[array1 objectAtIndex:i]];
                 k++;
             }
             i--:
        } else {
            if (array2 objectAtIndex:j] != [result objectAtIndex:k]){
                   [result addObject:[array2 objectAtIndex:j]];
                   k++;
             }
             j--:
        }

     }
     return result;
}

编辑:该代码中存在一些错误，因为 i可以变成负数，然后用于 objectAtIndex: ，这里只是为了演示思路，并不是给出开箱即用的代码方案