集合运算（补差）

Question

如何在不使用任何集合和 Linq 的情况下在 C# 中进行集补集和集差集？

我们有两个数组：

int [] arr1 = new int { 1, 2, 3, 4};
int[] arr2 = new int {3,4,5,6,7,8};

补数必须是：arr3 {5,6,7,8}，差数必须是：arr4 {1,2}.

我试过将一组添加到另一组，然后找到重复项，但没成功。

int numDups = 0, prevIndex = 0;

for (int i = 0; i < array.Length; i++)
{
    bool foundDup = false;
    for (int j = 0; j < i; j++)
    {
        if (array[i] == array[j])
        {
            foundDup = true;
            numDups++; // Increment means Count for Duplicate found in array.
            break;
        }                    
    }

    if (foundDup == false)
    {
        array[prevIndex] = array[i];
        prevIndex++;
    }
}

// Just Duplicate records replce by zero.
for (int k = 1; k <= numDups; k++)
{               
    array[array.Length - k] = '[=11=]';             
}

Answer 1

您可以创建两个列表，一个用于补码，另一个用于差值，迭代数组 A 并检查哪些包含在 B 中，哪些不包含 vice-versa，迭代 B 并检查哪些存在于 A 中。

更新：删除列表，仅使用数组，不使用 LINQ。

int[] arr1 = new int[]{ 1,2,3,4 };
int[] arr2 = new int[]{ 3,4,5,6,7,8 };

//We allocate the max possible size for each array, just for sanity
int[] arr3 = new int[arr1.Length + arr2.Length];
int[] arr4 = new int[arr1.Length + arr2.Length];

int difIndex = 0;
int compIndex = 0;

//Compute difference 
foreach(int i in arr1)
{
    bool found = false;
    foreach(int i2 in arr2)
    {
        if(i == i2)
        {
            found = true;
            break;
        }
    }

    if(!found)
        arr4[difIndex++] = i;
}

//Compute complement
foreach(int i in arr2)
{
    bool found = false;
    foreach(int i2 in arr1)
    {
        if(i == i2)
        {
            found = true;
            break;
        }
    }

    if(!found)
        arr3[compIndex++] = i;
}

//Remove unused items from array
Array.Resize(ref arr3, compIndex);
Array.Resize(ref arr4, difIndex);

Answer 2

在这个前提下，我们可以像这样创建函数 getComplement：

int[][] getComplement(int[] arr1, int[] arr2) {
    
    int[] complement = {};
    int[] difference = {};

    for (int i = 0; i < arr1.Length; i++)
    {
        bool isDupe = false;
        for (int j = 0; j < arr2.Length; j++) {
            if (arr1[i] == arr2[j] && !isDupe) {
                Array.Resize(ref complement, complement.Length + 1);
                complement[complement.GetUpperBound(0)] = arr2[j];
                isDupe = true;
            }
        }
        if (!isDupe) {
            Array.Resize(ref difference, difference.Length + 1);
            difference[difference.GetUpperBound(0)] = arr1[i];
        }
    }
    
    return new[] { complement, difference };
}

然后将其应用于我们的 2 个现有数组以获得所需的结果：

int [] arr1 = new int[] { 1, 2, 3, 4 };
int[] arr2 = new int[] { 3, 4, 5, 6, 7, 8 };
int[][] complementArr = getComplement(arr1, arr2);
int[][] differenceArr = getComplement(arr2, complementArr[0]);
int[] arr3 = differenceArr[1];
int[] arr4 = complementArr[1];

可以看到a working demo here.

Answer 3

集合 A 和 B 之间的区别是 A 中的所有元素不在 B 中。这些集合之间的互补是 B 中不在 A 中的所有元素。这些是镜像定义，所以你真的只需要写一个difference的方法，然后让compliment方法调用difference方法，输入参数取反即可。

（嗯，严格来说，恭维是 任何地方 中不在 A 中的所有元素，但这种区别在这里无关紧要。）

// Get an array of all elements in b that are not in a
// This is identical to calling GetDifference with the inputs reversed so lets just do that
int[] GetCompliment(int[] a, int[] b) { return GetDifference(b, a); }

// Get an array of all elements in a that are not in b
int[] GetDifference(int[] a, int[] b) 
{
    // Create the buffer array at the worst-case length which is the length
    // of a (where none of the elements in a are in b)
    int[] c = new int[a.Length];

    // Track how many elements we are actually ending up with
    int length = 0;

    // Loop through every element in a
    foreach (var ax in a)
    {
        bool found = false;
        // Loop through every element in b to see if it exists in a
        foreach (var bx in b)
        {
            if (ax == bx)
            {
                // If the element was found in b, there's no reason to keep looping
                found = true;
                break;
            }
        }

        // Only save the element if it was not found in b
        if (!found)
        {
            c[length] = ax;
            length++;
        }
    }

    // Create the result array using the length of actual elements found
    int[] result = new int[length];

    // Copy the relevant slice of the buffer array into the result array
    Array.Copy(c, result, length);

    // Return the result array
    return result;
}

用法：

int[] a = { 1, 2, 3, 4 };
int[] b = { 3, 4, 5, 6, 7, 8 };
int[] c = GetDifference(a, b);
        
foreach(var cx in c)
{
    Console.Write(cx + ", ");   
}
        
Console.WriteLine();
int[] d = GetCompliment(a, b);
        
foreach(var dx in d)
{
    Console.Write(dx + ", ");   
}

// Output:
// 1, 2, 
// 5, 6, 7, 8

DotNetFiddle

集合运算（补差）

Set operations (complement and difference)

c#

set

set-operations