在数组之间查找重复项

Question

假设您有两个长度恒定为3的整数数组，并且您始终确信给定的两个数组中的两个元素将具有相同的值。

因此，假设数组A有三个值：a，b，c。 数组B有三个值：d，e，f。

我们确定其中两个值将是相同的。我们被要求将这四个不同的值放入大小为4的数组中，使得输出数组C在索引1和2处具有来自数组A和B的相同值。在索引0和3处，它应该具有数组A和B的不同值。我已经实现了它，但对这个解决方案真的不满意...有人有更好的解决方案吗？除了将我的计数器放入数组中的解决方案... :)

int[] a = { 1, 201, 354 };
int[] b = { 404, 201, 354 };

int[] c = new int[4];

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

- kl.

---

不是的，我正在寻找不规则网络的三角测量，对于每个点，如果它周围有两个以上的三角形，我想测量角度... - kl.

我太懒了，不想写一个带有join和count重复项的LINQ。 - Dead account

谢谢你诚实的Ian :)))) - kl.

@kl：你关于三角测量的评论增加了你的问题的可信度 - 为什么不编辑一下以提供上下文呢？ - John K

Answer 1

非常抱歉，我重新仔细阅读了一遍，我认为这就是您想要的。请告知您的意见。:)

int[] same = a.Intersect(b).ToArray(); ;
int[] diff = a.Union(b).Except(same).ToArray();
int[] c = new int[] { diff[0], same[0], same[1], diff[1] };

- Sapph

---

是的，那就是这样的事情！ - Dead account

我可能误解了你的问题。你想让数组有共享值吗？{201, 354, 201, 354}？你的示例的预期输出是什么？ - Sapph

加油Sapph，把50行代码缩减到2行...你能做到的！ - Dead account

我重新编写了我的解决方案，以更准确地匹配问题...抱歉之前误解了，如果这符合您的需求，请告诉我。 - Sapph

+1 给马拉松用户图片（... 迄今为止最干净的解决方案）！ - FrustratedWithFormsDesigner

Answer 2

替换

// IRQ. 20100211. Deleted unncessary code

使用

var c = a.Concat(b).Distinct().ToArray();

更新：

新的：

var same = a.Intersect(b);
var c = a.Except(same).Concat(same).Concat(b.Except(same)).ToArray();

或者这些

var c = a.Except(b).Concat(a.Intersect(b)).Concat(b.Except(a));
var c = a.Except(b).Concat(a).Concat(b).Distinct();

- dh.

Answer 3

你所需要的仅是两个数组的集合（集合中最多只包含每个元素一次）。C++的解决方案如下：

#include <set>

int main () {
    int a[] = { 1,2,3 };
    int b[] = { 4,2,3 };

    std::set<int> s(a, a+3);
    s.insert(b, b+3);
}

- rmn

Answer 4

如果您使用LINQ，以下代码就足够了：

int[] c = a.Union(b).ToArray();

Union检查重复项，因此不需要进行进一步的检查：

返回：一个包含来自两个输入序列的元素（不包括重复项）的System.Collections.Generic.IEnumerable。

- Aistina

Answer 5

这里有一个很酷的C(++)解决方案

int a[3], b[3]; /* the two arrays */
int c[4]; /* target */
int s=0, t=0, k;
int i;
for (i=0;i<3;i++) { k = a[i]-b[i]; s += k; t += k*(a[i]+b[i]); }

/* At this point s is the difference of the two distinct elements
   and t is the difference of their squares, i.e. s = x - y and t = x^2 - y^2
   because (x-y)(x+y) = x^2-yx+yx-y^2 = x^2-y^2
   Because the two elements are distinct, s != 0 and we can easily divide t
   by s to get (x + y), from which then we have
   s == x - y
   t == x + y
   i.e. x = (s+t)/2 and y=(t-s)/2 */

t /= s;
int x = (s + t) / 2;
int y = (t - s) / 2;

/* Now x, y are the distinct elements, x from array a and y from array b */
/* Fill in the results */
c[0] = x;
c[3] = y;
/* If a[0] is non-shared, then a[1] must be the first shared element; otherwise a[0] */
c[1] = (a[0] == x ? a[1] : a[0]);
/* If a[2] is non-shared, then a[1] must be the last shared element; otherwise a[2] */
c[2] = (a[2] == x ? a[1] : a[2]);

示例：a = {1, 3, 5}，b = {3, 5, 2}

s = (1-3)+(3-5)+(5-2) = -2-2+3 = -1
t = (1-3)*(1+3)+(3-5)*(3+5)+(5-2)*(5+2) = -8-16+21 = -3
t / s = 3
x = (-1 + 3) / 2 = 1
y = (3 - (-1)) / 2 = 2
c[0] = 1
c[3] = 2
c[1] = 3
c[2] = 5

所以C语言得到了值{1,3,5,2}，正如所期望的！

为了好玩，这里有一个更紧凑的版本：

/* Declarations */
int a[3], b[3], c[4];
int s = 0, t = 0, k, i;

/* Actual algorithm */
for (i = 0; i < 3; i++) { s += (k = a[i]-b[i]); t += k * (a[i]+b[i]); }
t /= s;
c[0] = (s + t) >> 1;
c[3] = (t - s) >> 1;
c[1] = (a[0] == x ? a[1] : a[0]);
c[2] = (a[2] == x ? a[1] : a[2]);

请注意，如果将问题概括为共享n-1个元素并且两个数组中都有一个唯一元素，则此算法的时间复杂度为O(n)，而基于集合交集和/或并集的算法通常为O(n log n) :)

- Antti Huima

---

这是我找到它的方法：我首先考虑将所有6个元素进行异或，这样你就会得到x^y，但从中你无法直接恢复x^y，所以我想到了减法，a[0]+a[1]+a[2]-b[0]-b[1]-b[2]，这给出了x-y...但这有同样的问题。因此，你需要另一个线性独立的项，这样你才能解出x和y。当我意识到x^2-y^2和x-y一起很容易地产生x和y时，这些部分就像拼图一样拼在了一起。 - Antti Huima

Answer 6

更快？

using System;
using System.Linq;
using sw = System.Diagnostics.Stopwatch;
class Program
{
    static void Main()
    {
        int[] a = new int[] { 1, 2, 3 },  // try: a={1,2,2} b={2,2,3}
              b = new int[] { 4, 2, 3 }, c = new int[4];
        sw sw = sw.StartNew();
        for (int i = 5000000; i > 0; i--) { dssd1(a, b, c); dssd1(b, a, c); }
        Console.Write(sw.ElapsedMilliseconds);
        Console.Read();
    }

    static void dssd0(int[] a, int[] b, int[] c)               // 6710 ms.
    {
        int[] s = a.Intersect(b).ToArray();        // same
        int[] d = a.Union(b).Except(s).ToArray();  // diff
        c[0] = d[0]; c[1] = s[0]; c[2] = s[1]; c[3] = d[1];
    }

    static void dssd1(int[] a, int[] b, int[] c)               //   61 ms.
    {
        if (a[0] != b[0] && a[0] != b[1] && a[0] != b[2])
        { c[0] = a[0]; c[1] = a[1]; c[2] = a[2]; goto L0; }
        if (a[1] != b[0] && a[1] != b[1] && a[1] != b[2])
        { c[0] = a[1]; c[1] = a[0]; c[2] = a[2]; goto L0; }
        c[0] = a[2]; c[1] = a[0]; c[2] = a[1];
    L0: if (b[0] != c[1] && b[0] != c[2]) { c[3] = b[0]; return; }
        if (b[1] != c[1] && b[1] != c[2]) { c[3] = b[1]; return; }
        c[3] = b[2];
    }
}

最快的？

    L0: c[3] = b[0] != c[1] && b[0] != c[2] ? b[0] :           //   49 ms.
        b[1] != c[1] && b[1] != c[2] ? b[1] : b[2];

- P_P

Answer 7

这部分

    if (a[0] == b[0]) { counter0++; }
    if (a[0] == b[1]) { counter0++; }
    if (a[0] == b[2]) { counter0++; }

    if (a[1] == b[0]) { counter1++; }
    if (a[1] == b[1]) { counter1++; }
    if (a[1] == b[2]) { counter1++; }

    if (a[2] == b[0]) { counter2++; }
    if (a[2] == b[1]) { counter2++; }
    if (a[2] == b[2]) { counter2++; }

可能可以重写为

for (i=0; i<3; i++)
{
    for (j=0; j<3; j++)
    {
         switch(i)
         {
              case 0:
              if (a[i] == b[j]) { counter0++; }
              break;
              case 1:
              if (a[i] == b[j]) { counter1++; }
              break;
              case 2:
              if (a[i] == b[j]) { counter2++; }
              break;
          }
     }
}

另一部分与其他计数器应该类似地编写。然后，您可以将其重构为单独的方法，并将数组和计数器传递给它。

另一个选项可能是LINQ，但我不确定如何编写类似这样的内容。

（尚未尝试编译此内容，但思路清晰吗？）

更新： 如果您可以将计数器放入数组中，则可能会起作用：

for (i=0; i<3; i++)
{
    for (j=0; j<3; j++)
    {
        if (a[i] == b[j]) { counters[i]++; }

     }
}

- FrustratedWithFormsDesigner

---

只是一个小提示：我建议使用foreach循环而不是for循环。我发现它们更容易阅读和处理。 - Anne Schuessler

@Anne：但是算法需要i的值... foreach(var x in a) { i++; } 可能更糟糕。 - Jimmy

@Anne Schuessler：很可能，我相信还有许多其他小的改进可以做。例如，计数器可以在计数器数组中，这样开关/情况可以被放弃并替换为“counters [i] ++;”。 - FrustratedWithFormsDesigner

@Jimmy：是的，我想你是对的。我在尝试我的“解决方案”时意识到，我可能需要将foreach更改回for循环才能访问数组中每个项的位置。 - Anne Schuessler

Answer 8

我非常确定我不理解这个问题。

你说：

我们确定两个值将相同。 我们被要求将这四个不同的值放入其中

你指的是哪四个不同的值？ 是相同的两个吗？ 因为“these”一词就是指它们。

您的意思是：将4个唯一的值放入数组中吗？

所以：

1, 2, 3
2, 3, 4

变成了：

1, 2, 3, 4？

那很容易：

int[] c = a.Concat(b).Distinct().ToArray();

这个使用了 .NET 3.5 的 Linq 扩展方法。如果你没有使用 .NET 3.5，可以这样做：

Dictionary<int, int> c1 = new Dictionary<int, int>();
foreach (var x in a)
    c1[x] = 1;
foreach (var x in b)
    c1[x] = 1;
int[] c = new List<int>(c1.Keys).ToArray();

现在，如果您需要顺序如下：

1. 第一个仅出现一次的值
2. 第一个出现两次的值
3. 第二个出现两次的值
4. 第二个仅出现一次的值

那么恐怕我没有一行代码可以为您提供，需要再考虑一下。

我可以问一下上下文是什么吗？为什么有这个要求？

- Lasse V. Karlsen

---

第二个版本依赖于未指定的行为（字典键的排序）。 - Jimmy

两个版本，Linq和非Linq，都按照问题要求输出了错误的顺序。 - Lasse V. Karlsen

OrderedDictionary应该可以工作。所请求的顺序是插入顺序。 - Jimmy

Answer 9

bool isUsed[6]={true, true, true, true, true, true};

int values[6];

int valuesCount = 0;

int i,j;

for( i = 0 ; i < 3 ; i++)
{
   bool goodValue = true;
   for ( j = 0; j < valuesCount; j++)
   {
       if(values[j] == a[i])
       {
           isUsed[j] = false;
           goodValue = false;
           break;
       }
   }
   if(goodValue)
   {
       values[valuesCount++]=a[i];
   }
}

//same for b[i]

for( i = 0 ; i < valuesCount; i++)
{ 
   if( isUsed[i] ) printf("%i ", values[i]);
}

- botismarius

---

谢谢您的修复！我尝试了很多次来格式化它，但是都没有成功:D而且也无法删除回复... - botismarius

Answer 10

不要使用counter1、counter2、counter3这样的变量名：

counter[3];

从那里开始，很多事情都变得更容易了。首先，你可以在循环中引用所有内容。

- Dean J