之間重複假設你是某一固定的長度爲3的整數兩個數組，你總是很肯定的給出了兩個arrray的兩個元素都會有相同的價值觀。查找陣列
所以假設數組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]);
}
對不起，我重新仔細閱讀，我認爲這是你想要的。請指教。 :)
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] };
是的，這是事情！ – 2010-02-11 21:26:21
這隻給出1和404 ... – 2010-02-11 21:26:41
我可能誤解了你的問題。你想讓數組擁有共享的值嗎？ {201,354,201,354}？你的例子的預期輸出是什麼？ – Sapph 2010-02-11 21:29:49
這部分
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，但我不知道到底該怎麼寫這樣的事情。
（沒試過編譯這一點，但這個想法清楚了嗎？）
UPDATE： 如果你可以把計數器陣列中的，這可能工作：
for (i=0; i<3; i++)
{
for (j=0; j<3; j++)
{
if (a[i] == b[j]) { counters[i]++; }
}
}
謝謝，但總體來說你有更好的主意嗎？ – 2010-02-11 21:22:16
只是一個小提示：我建議使用foreach循環而不是for循環。我發現他們更容易閱讀和處理。 – 2010-02-11 21:31:44
@安妮：但算法需要我的值.... foreach（var x in a）{i ++; }可能更糟。 – Jimmy 2010-02-11 21:37:40
我我很確定我不明白這個問題。
你說：
我們相信，兩個值將是相同的。我們被要求把這四個不同的值
你指哪四個不同的值？這兩個是一樣的嗎？因爲這就是「這些」這個詞所指的。
你的意思是：取4個獨特的價值觀，並把它們放到一個數組？
這樣：
1，2，3
2，3，4
變爲：
1，2，3，4？
這很簡單：
int[] c = a.Concat(b).Distinct().ToArray();
它使用.NET 3的LINQ的擴展方法。5.如果你不是在.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();
現在，如果你需要的順序是這樣的：
那麼恐怕我沒有一句話給你，將不得不多思考一下。
我可以問一下上下文是什麼嗎？爲什麼這個要求？
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]);
}
修復了您的格式。 – Aistina 2010-02-11 21:39:46
感謝您的修正！我嘗試了很多次格式化，但無法成功：D，並且無法刪除響應... – botismarius 2010-02-12 11:20:04
相反計數器1，計數器2的，計數器3：
counter[3];
很多事情就從那裏更容易。開始時可以參考循環中的所有內容。
我想出了這個作爲初稿，但我認爲它可能需要一些改進。它也不符合在位置1和2具有重複項以及在陣列中具有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;
}
}
更換
// 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();
Lasse已經提到了這一點，我同意這將不起作用:) – 2010-02-11 21:50:19
你要找的只是一組的兩個陣列（一套包含每一個元素一次最多）的。 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);
}
我想給出一個簡短的答案。但是，它假定輸入是正確的。
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'
如果您在您的處置有LINQ，下面的代碼就足夠了：
int[] c = a.Union(b).ToArray();
重複項聯合檢查，因此沒有進一步的檢查是必要的：
返回： System.Collections.Generic.IEnumerable ，它包含來自 輸入序列的元素，不包括重複項。
下面是一些簡單的代碼，但它假定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];
這裏用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）:)
+1 - 太棒了！ – Eric 2010-02-12 02:57:56
下面是我如何找到它的：我首先想到了把所有6個元素異或，所以你最終會得到x^y，但是你不能直接恢復x^y，所以我想到了減法， a [0] + a [1] + a [2] -b [0] -b [1] -b [2]，它給你xy ...但是也有同樣的問題。所以你需要另一個線性獨立的術語，以便你可以解決x和y。然後，當我意識到x^2-y^2和x-y一起容易地產生如上所示的x和y時，這些碎片會咬合在一起。 – 2010-02-12 05:36:33
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<int>();
Array.Sort(arrA);
Array.Sort(arrB);
for(int i=0;i<arrA.Length;i++)
{
if(arrB.Contains(arrA[i]))
{
aList.Add(arrA[i]);
}
}
return aList.ToArray();
}
作業問題？ – Tim 2010-02-11 21:16:09
不是所有:)，我正在尋找不規則網絡的三角剖分，如果每個點都有其周圍的兩個以上的三角形，我想測量角度... – 2010-02-11 21:18:39
即時通訊懶得寫LINQ加入，計數重複。 – 2010-02-11 21:19:02