从另一个数组中移除一个数组的有效算法

本文关键字：数组 一个 有效 算法 另一个 | 更新日期: 2023-09-27 18:08:51

我想知道是否有人知道更好(如更快)的算法/解决方案来解决我的问题:

在我的程序中，我有一个单元数组，我想从中删除包含在另一个单元数组中的项。但是，我不能使用集合的并集，因为我需要保留重复的值。解释得很糟糕，但这个例子应该会让它更清楚一些:

    uint[] array_1 = new uint[7] { 1, 1, 1, 2, 3, 4, 4};
    uint[] array_2 = new uint[4] { 1, 2, 3, 4 };
    uint[] result = array_1 .RemoveRange(array_2);
    // result should be: { 1, 1, 4 }

这是我目前最好的主意;但是它相当慢:

    public static uint[] RemoveRange(this uint[] source_array, uint[] entries_to_remove)
    {
        int current_source_length = source_array.Length;
        for (int i = 0; i < entries_to_remove.Length; i++)
        {
            for (int j = 0; j < current_source_length; j++)
            {
                if (entries_to_remove[i] == source_array[j])
                {
                    // Shifts the entries in the source_array.
                    Buffer.BlockCopy(source_array, (j + 1)* 4 , source_array, j * 4, (current_source_length - j) * 4);
                    current_source_length--;
                    break;
                }
            }
        }
        uint[] new_array = new uint[current_source_length];
        Buffer.BlockCopy(source_array, 0, new_array, 0, current_source_length * 4);
        return new_array;
    }
所以，有人能想出一个更聪明的方法来实现我想要的吗?

谢谢!

从另一个数组中移除一个数组的有效算法

如果使用Dictionary<uint,int>使用整数数字作为键，并将数字出现的次数作为值呢?

var source = new Dictionary<uint,int>();
source.Add(1,3);
source.Add(2,1);
source.Add(3,1);
source.Add(4,2);
var remove = new uint[]{ 1, 2, 3, 4 };
for (int i = 0; i<remove.Length; i++) {
    int occurences;
    if (source.TryGet(remove[i], out occurences)) {    
        if (occurences>1) {
            source[remove[i]] = occurences-1;
        } else {
            source.Remove(remove[i]);
        }
    }
}

这将做你想要的，据我所知，他们的关键是引用计数的出现次数，然后使用剩余的引用计数(如果> 0)作为一个数字必须发出的次数:

public static uint[] RemoveRange(this uint[] source_array, uint[] entries_to_remove)
{
    var referenceCount = new Dictionary<uint, int>();
    foreach (uint n in source_array)
    {
        if (!referenceCount.ContainsKey(n))
            referenceCount[n] = 1;
        else
            referenceCount[n]++;
    }
    foreach (uint n in entries_to_remove)
    {
        if (referenceCount.ContainsKey(n))
            referenceCount[n]--;
    }
    return referenceCount.Where(x => x.Value > 0)
                         .Select(x => Enumerable.Repeat(x.Key, x.Value))
                         .SelectMany( x => x)
                         .ToArray();
}

EDIT:这对您没有帮助，因为您希望保留副本。
我把它留在这里给那些不想要副本的人。

从第二个列表创建一个HashSet<T>，然后用哈希集的Contains方法调用List<T>.RemoveAll。

var unwanted = new HashSet<uint(...);
list.RemoveAll(unwanted.Contains);

如果你不想就地删除它们，你可以使用LINQ:

list.Except(unwanted);

Except将构建两个哈希集并每次返回一个项目(延迟执行)0

如果数组未排序，则对其排序。初始化3个索引为0。"s"(源)和"d"(dest)索引大数组A，"r"索引"toRemove"数组b。

   While r<B.length,
           While B[r] > A[s], A[d++]= A[s++].   
            If B[r]==A[s], s++.
             r++.
    Endwhile. 
    While s<A.length,  A[d++]= A[s++].
     A.length = d.

这不需要额外的空间，并且运行时间为O(N)，(如果它们最初未排序，则运行时间为nlgn)，与原始解决方案的N^2 I相比。

你可以尝试在这里使用Linq，

var resultarray = array1.Except(array2);
相关文章：