查找数组之间的重复项
假设您有两个常量长度为3的整数数组，并且您始终确定给定两个arrray的两个元素将具有相同的值。
所以假设数组A有三个值：a，b，c。 和数组B有三个值：d，e，f。
我们确信其中两个值是相同的。 我们被要求将这四个不同的值放在一个大小为4的数组中，这样输出数组C应该在索引1和2中具有来自数组A和B的相同值，并且在索引0和3处它应该具有不同的值arraysA和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]); } 对不起，我仔细阅读了，我觉得这就是你想要的。 请指教。 🙂
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] };
你要找的只是一组两个数组（set最多包含一个元素）。 c ++中的解决方案：
#include int main () { int a[] = { 1,2,3 }; int b[] = { 4,2,3 }; std::set s(a, a+3); s.insert(b, b+3); }
如果您有LINQ可供使用，则以下代码就足够了：
int[] c = a.Union(b).ToArray();
Union检查重复项，因此无需进一步检查：
返回：System.Collections.Generic.IEnumerable，包含两个输入序列中的元素，不包括重复项。
更换
// 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();
这是一个很酷的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, ie s = x - y and t = x^2 - y^2 because (xy)(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 ie x = (s+t)/2 and y=(ts)/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）:)
而不是counter1，counter2，counter3：
counter[3];
从那里开始，很多事情都变得容易了。 你可以参考循环中的所有内容。
我很确定我不明白这个问题。
你说：
我们确信其中两个值是相同的。 我们被要求提出这四个不同的价值观
您指的是哪四个不同的值？ 两个是一样的吗？ 因为这就是“这些”所指的那个词。
你的意思是：取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 c1 = new Dictionary(); foreach (var x in a) c1[x] = 1; foreach (var x in b) c1[x] = 1; int[] c = new List(c1.Keys).ToArray();
现在，如果您需要订单：
- 第一个只发生一次的值
- 发生两次的第一个值
- 发生两次的第二个值
- 第二个值只发生一次
然后我担心我没有为你做单线，你将不得不考虑更多。
我可能会问上下文是什么？ 为什么这个要求？
我提出这是初稿，但我认为它可能需要一些改进。 它也不满足在位置1和2处具有重复项以及在arrays中具有0和3处的唯一数字的要求。 无论如何我以为我会发布它，所以你可以知道它的外观：
int[] a = { 1, 201, 354 }; int[] b = { 404, 201, 354 }; int[] c = new int[ 4 ]; // Start by just copying over one of the arrays completely. a.CopyTo( c, 0 ); // Loop through b and compare each number against each // each number in a. foreach( int i in b ) { // Assume that you're not dealing with a duplicate bool found = true; foreach( int j in a ) { // If you find a duplicate, set found to false if( i == j ) { found = false; } } // If you haven't found a duplicate this is the // number you want - add it to the array. if (found == true) { c[3] = i; } }
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]); }
这部分
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]++; } } }
我想简单回答一下。 但是它假定输入是正确的。
int c1, c2, i; c1 = a[0] == b[0] ? 0 : (a[0] == b[1] ? 1 : 2); // index of a[0] in array 'b' c2 = a[1] == b[0] ? 0 : (a[1] == b[1] ? 1 : 2); // index of a[1] in array 'b' for(i=0; i<2; i++) Console.WriteLine(a[i]); Console.WriteLine(b[3-c1-c2]); // looks quite hacky but it is actually element of 'b' not in array 'a'
这是一些简单的代码，但它假设a和b中的值始终为正。
int[] a = { 1, 201, 354 }; int[] b = { 404, 201, 354 }; int[] c = { -1, -1, -1, -1}; for(int i = 0; i < 3; i++){ int notfound = 1; for(int j = 0; j < 3; j++){ if(b[j] == -1) continue; if(a[i] == b[j]){ b[j] = -1; if(c[1] == -1) c[1] = a[i]; else c[2] = a[i]; notfound = 0; break; } } if(notfound) c[0] = a[i]; } int k = 0; while(b[k++] == -1); c[3] = b[k];
我没有测试过，但希望你能得到这个想法。 这使用非常少的额外空间（只是未发现的空间，可以做成布尔值和索引变量）并且应该非常快。
int[] a = { 204, 534, 1 }; int[] b = { 204, 534, 401 }; int[] c = new int[4]; int x = 3, y = 3, k = 1; for(int i=0; i<3; i++) for(int j=0; j<3; j++) if (a[i] == b[j]) { c[k++] = a[i]; x -= i; y -= j; break; } c[0] = a[x]; c[3] = b[y];
Sapph提供了一个尽可能干净的答案，但如果性能非常重要，那就是一个答案。 .NET数组边界检查可能会增加一些开销，但在C中，这会编译为64条指令而没有分支。
int[] a = { 204, 534, 1 }; int[] b = { 204, 534, 401 }; int[] c = new int[4]; // pick the value from a that is not in b for c[0] // a[0] not in b is implied by a[1] in b and a[2] in b int a1_not_in_b = Convert.ToInt32(a[1] != b[0] & a[1] != b[1] & a[1] != b[2]); int a2_not_in_b = Convert.ToInt32(a[2] != b[0] & a[2] != b[1] & a[2] != b[2]); // bitfield of 2 bit values equivalent to the array {0,1,2,0,1} int idxs = 0 | 1 << 2 | 2 << 4 | 0 << 6 | 1 << 8; // if a[1] not in b start at 1, if a[2] not in b start at 2, else start at 0 idxs >>= 2*a1_not_in_b | 4*a2_not_in_b; c[0] = a[(idxs >> 0) & 3]; c[1] = a[(idxs >> 2) & 3]; c[2] = a[(idxs >> 4) & 3]; // pick the value from b that is not in a // b[0] not in a is implied by b[1] in a and b[2] in a int b1_not_in_a = Convert.ToInt32(a[0] != b[1] & a[1] != b[1] & a[2] != b[1]); int b2_not_in_a = Convert.ToInt32(a[0] != b[2] & a[1] != b[2] & a[2] != b[2]); c[3] = b[b1_not_in_a | 2*b2_not_in_a];
快点？
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];
这个怎么样？
private static int[] FindDuplicates(int[] arrA,int[] arrB) { var aList=new List(); Array.Sort(arrA); Array.Sort(arrB); for(int i=0;i