C#算法合并两个排序数组而不重复

Question

我需要编写一种算法，将两个已排序的整数数组合并为一个没有重复的数组。

我设法合并了它们，但我不确定如何从最终数组中删除重复项，同时用两个数组的总和启动合并数组似乎也不正确，因为重复项将默认 int 值为 0。

public static int[] MergeArrays(int[] firstArray, int[] secondArray)
{
    var firstArrayLength = firstArray.Length;
    var secondArrayLenght = secondArray.Length;
    var mergedArray = new int[firstArrayLength + secondArrayLenght];
    var i = 0;
    var j = 0;
    var k = 0;

    while (i < firstArrayLength && j < secondArrayLenght)
    {
        if (firstArray[i] < secondArray[j])
        {
            mergedArray[k] = firstArray[i];
            i++;
        }
        else
        {
            mergedArray[k] = secondArray[j];
            j++;
        }

        k++;
    }

    while (i < firstArrayLength)
    {
        mergedArray[k++] = firstArray[i++];
    }

    while (j < secondArrayLenght)
    {
        mergedArray[k++] = secondArray[j++];
    }

    return mergedArray;
}

如果不使用 LINQ 或特定于数组的方法，您将如何做到这一点？

Answer 1

你快到了。您已使合并算法的主要部分正常工作。

您只剩下两件事要做：

Return 一个正确大小的数组。由于您已经在 k 变量中跟踪合并数组的大小，因此您可以使用它来使用 Array.Resize(ref mergedArray, k);.
调整数组大小
您想对数组进行重复数据删除。因为您按排序顺序维护合并数组，所以您可以在向数组添加新值之前检查重复值，如果它已经在合并数组的末尾则跳过添加它。注意一定要小心处理合并数组当前为空的情况！

尽量保留您的原始代码，这是一个解决方案。

它引入了一个 candidate 值，我们用它来检查要插入到结果数组中的值是否已经在该数组中。它还在返回之前将数组调整为正确的大小：

public static int[] MergeArrays(int[] firstArray, int[] secondArray)
{
    var firstArrayLength  = firstArray.Length;
    var secondArrayLength = secondArray.Length;
    var mergedArray       = new int[firstArrayLength + secondArrayLength];
    var i                 = 0;
    var j                 = 0;
    var k                 = 0;
    int candidate;

    while (i < firstArrayLength && j < secondArrayLength)
    {
        if (firstArray[i] < secondArray[j])
        {
            candidate = firstArray[i];
            i++;
        }
        else
        {
            candidate = secondArray[j];
            j++;
        }

        if (k == 0 || mergedArray[k-1] != candidate)
        {
            mergedArray[k] = candidate;
            k++;
        }
    }

    while (i < firstArrayLength)
    {
        candidate = firstArray[i++];

        if (k == 0 || mergedArray[k-1] != candidate)
        {
            mergedArray[k] = candidate;
            k++;
        }
    }

    while (j < secondArrayLength)
    {
        candidate = secondArray[j++];

        if (k == 0 || mergedArray[k-1] != candidate)
        {
            mergedArray[k] = candidate;
            k++;
        }
    }

    Array.Resize(ref mergedArray, k);
    return mergedArray;
}

你说你不能使用“特定于数组”的方法。如果这排除了 Array.Resize() 的使用，那么您可以改为执行以下操作：

int[] result = new int[k];

for (int i = 0; i < k; ++i)
    result[i] = mergedArray[k];

return result;

这个 more-or-less 做 Array.Resize() 做的事 - 它创建一个正确大小的新数组并将源数组的元素复制到其中。

您可能认为您可以使用 Linq 来使用

var result = array1.Union(array2).ToArray();

这个问题是结果没有排序，所以给出

int[] array1 = {1, 3, 5, 7, 9};
int[] array2 = {2, 4, 6, 8, 10};
int[] merged = array1.Union(array2).ToArray();

Console.Write(string.Join(", ", merged));

输出为 1, 3, 5, 7, 9, 2, 4, 6, 8, 10，未排序。

您必须添加排序步骤：

int[] merged = array1.Union(array2).OrderBy(i => i).ToArray();

但是现在我们已经将 O(N) 算法变成了 O(N.Log(N)) 算法，因为 OrderBy() 是 O(N.Log(N))。这是否真的是一个问题取决于您的情况。

另请注意，您还可以通过返回 mergedArray.Distinct().ToArray() 在返回数组之前从数组中删除重复项，但这会引入不必要的额外数据副本以及额外的 O(N) 操作。如果这是家庭作业，那可能不是导师要找的！

最后一点，您可能会注意到有一些重复的代码用于检查重复值。您可以将该代码放入本地函数中以避免重复。如果这样做，最终方法可能如下所示：

public static int[] MergeArrays(int[] firstArray, int[] secondArray)
{
    var firstArrayLength  = firstArray.Length;
    var secondArrayLength = secondArray.Length;
    var mergedArray       = new int[firstArrayLength + secondArrayLength];
    var i                 = 0;
    var j                 = 0;
    var k                 = 0;

    void addIfNotDupe(int candidate) // Local function.
    {
        if (k != 0 && mergedArray[k - 1] == candidate)
            return;

        mergedArray[k++] = candidate;
    }

    while (i < firstArrayLength && j < secondArrayLength)
    {
        addIfNotDupe(firstArray[i] < secondArray[j] ? firstArray[i++] : secondArray[j++]);
    }

    while (i < firstArrayLength)
    {
        addIfNotDupe(firstArray[i++]);
    }

    while (j < secondArrayLength)
    {
        addIfNotDupe(secondArray[j++]);
    }

    Array.Resize(ref mergedArray, k);
    return mergedArray;
}

C#算法合并两个排序数组而不重复

C# Algorithm to merge two sorted arrays without duplicates

c#

array-merge