2

所以，我发现了一个有趣的问题，给你 2 个排序数组，你的任务是将它们组合成一个新数组并保持排序。此外，找到你的程序的效率。我的代码正常工作，但我不确定效率。我认为它是 O(n)，因为我使用 while 循环遍历数组的每个元素。有小费吗？有没有办法让这更有效？O(n) 是否正确？这是代码：

class mergesorted{
    static void Main(string[] args){
        int[] x = { 1, 3, 7};
        int[] y = { 2, 4, 5, 6, 15};
        int[] retrieval =  answer(x, y);

        for (int i = 0; i < retrieval.Length; i++){
            Console.WriteLine(retrieval[i]);                
        }
        Console.ReadLine();
    }

    public static int[] answer(int[] x, int[] y)
    {
        int[] a = x;
        int[] b = y;
        int abc = 0; //counter for a
        int abc2 = 0; //counter for b
        int i = 0; //counter for index of new array
        Boolean flagA = true; //if flag changed, array is exhaused
        Boolean flagB = true;
        int[] newarray = new int[a.Length+b.Length]; //so size is 7

        while (abc < a.Length && abc2 < b.Length){
            if (a[abc] < b[abc2]){
                newarray[i] = a[abc];
                abc++;
            }
            else{
                newarray[i] = b[abc2];
                abc2++;
            }

            if (abc >= a.Length){
                flagA = true;
                flagB = false;
            }

            else if (abc2 >= b.Length){
                flagA = false;
                flagB = true;
            }
            i++;
        }

        if (flagA == false){
            while (abc < a.Length){
                newarray[i] = a[abc];
                abc++;
                i++;
            }
        }
        else if (flagB == false){
            while (abc2 < b.Length){
                newarray[i] = b[abc2];
                abc2++;
                i++;
            }
        }
        return (newarray);
    }
}
4

1 回答 1

3

你有很多多余的测试。但是你的算法是 O(N)，因为它接触每个元素一次。你不能做得比这更好（在一般情况下），因为构建最终数组是 O(N)。

在一个数组比另一个数组大得多并且你有一个 O(1) 插入（或移动）操作的特殊情况下，你可以制定一个 O(A log B) 的算法，其中 A 是较小的列表，B 是较大列表中的条目数。例如，如果一个数组有 1,000,000 个对象，而另一个数组只有 2 个，您可以使用二分搜索找出在 1,000,000 个对象列表中移动另一个列表中的两个对象中的每一个的位置。如果这两个列表的大小大致相同，这将无济于事。

于 2013-09-23T04:57:23.503 回答