两个有序整形数组找出二者相同的元素和不同的元素
时间:2010-09-30 来源:chenping2008
两个有序整形数组找出二者相同的元素和不同的元素,算法如下:(包含了测试代码)
Int32 lena = a.Length; Int32 lenb = b.Length; Int32 ia = 0; Int32 ib = 0; while (ia <= lena - 1 && ib <= lenb - 1) { if (a[ia] < b[ib]) { if (same.Count > 0 && a[ia] == same[same.Count - 1]) { ia++; continue; } noSame.Add(a[ia]); ia++; continue; } if (a[ia] == b[ib]) { if (same.Count >0 && a[ia] != same[same.Count - 1]) { same.Add(a[ia]); ia++; ib++; continue; } if (same.Count == 0 || a[ia] != same[same.Count - 1]) { same.Add(a[ia]); } ia++; ib++; continue; } if(a[ia]>b[ib]) { if ( same.Count>0 && b[ib] != same[same.Count - 1]) { noSame.Add(b[ib]); ib++; continue; } if (same.Count > 0 && b[ib] == same[same.Count - 1]) { ib++; continue; } noSame.Add(b[ib]); ib++; continue; } }
int nowia = ia - 1; while (ia <= lena - 1) { if (nowia < 0) { noSame.Add(a[ia]); } else { if (a[ia] != a[nowia]) { noSame.Add(a[ia]); } } ia++; nowia++; }
int nowib = ib - 1; while (ib <= lenb - 1) { if (nowib < 0) { noSame.Add(b[ib]); } else { if (b[ib] != b[nowib]) { noSame.Add(b[ib]); } } ib++; nowib++; } return; } 测试代码: [TestMethod()] public void SearchElementTest() { LookSameOrNoSameElement target = new LookSameOrNoSameElement(); // TODO: Initialize to an appropriate value int[] a = null; // TODO: Initialize to an appropriate value int[] b = null; // TODO: Initialize to an appropriate value IList<int> same = new List<int>(); // TODO: Initialize to an appropriate value IList<int> noSame = new List<int>(); // TODO: Initialize to an appropriate value
target.SearchElement(a,b,same,noSame); Assert.IsTrue(same.Count == 0); Assert.IsTrue(noSame.Count==0);
same = new List<int>(); noSame = new List<int>(); a = new int[6] { 3,7,10,11,30,40}; b = null; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count==0); Assert.IsTrue(noSame.Count==6); Assert.IsTrue(Judge(a, noSame));
same = new List<int>(); noSame = new List<int>(); a = null; b =new int[5]{4,7,20,30,40}; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 0); Assert.IsTrue(noSame.Count ==5); Assert.IsTrue(Judge(b, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[6] { 3, 7, 10, 11, 30, 40 }; b = new int[5] { 4, 7, 20, 30, 40 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count ==3); Assert.IsTrue(Judge(new int[] { 7,30,40 }, same)); Assert.IsTrue(noSame.Count ==5); Assert.IsTrue(Judge(new int[]{3,4,10,11,20}, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[6] { 3, 7, 10, 11, 30, 40 }; b = new int[6] { 3, 7, 20, 30, 40,100 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count ==4); Assert.IsTrue(Judge(new int[] { 3,7, 30, 40 }, same)); Assert.IsTrue(noSame.Count ==4); Assert.IsTrue(Judge(new int[] { 10, 11, 20,100 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[1] { 0 }; b = new int[1] { 0}; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count ==1); Assert.IsTrue(Judge(new int[] { 0 }, same)); Assert.IsTrue(noSame.Count == 0);
same = new List<int>(); noSame = new List<int>(); a = new int[2] { 0 ,9}; b = new int[2] { 0,9 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count ==2); Assert.IsTrue(Judge(new int[] { 0,9 }, same)); Assert.IsTrue(noSame.Count == 0);
same = new List<int>(); noSame = new List<int>(); a = new int[2] { 0, 9 }; b = new int[2] { 10,20}; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count ==0); Assert.IsTrue(noSame.Count == 4); Assert.IsTrue(Judge(new int[4]{0,9,10,20},noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[6] { 3, 7, 7, 11, 30, 40 }; b = new int[5] { 4, 7, 20, 30, 40 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 3); Assert.IsTrue(Judge(new int[] { 7, 30, 40 }, same)); Assert.IsTrue(noSame.Count == 4); Assert.IsTrue(Judge(new int[] { 3, 4, 11, 20 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[2] {0,9}; b = new int[3] { 0,9,9 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 2); Assert.IsTrue(Judge(new int[] { 0,9 }, same)); Assert.IsTrue(noSame.Count == 0);
same = new List<int>(); noSame = new List<int>(); a = new int[2] { 0, 9 }; b = new int[4] { 0, 9, 10,10}; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 2); Assert.IsTrue(Judge(new int[] { 0, 9 }, same)); Assert.IsTrue(noSame.Count ==1); Assert.IsTrue(Judge(new int[] { 10 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[2] { 0, 9 }; b = new int[5] { 0, 9, 10, 10,11 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 2); Assert.IsTrue(Judge(new int[] { 0, 9 }, same)); Assert.IsTrue(noSame.Count == 2); Assert.IsTrue(Judge(new int[] { 10,11 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[4] { 0, 9 ,9,10}; b = new int[5] { 0, 9, 9,9, 11 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 2); Assert.IsTrue(Judge(new int[] { 0, 9 }, same)); Assert.IsTrue(noSame.Count == 2); Assert.IsTrue(Judge(new int[] { 10, 11 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[4] { 5, 9, 9, 10 }; b = new int[5] { 0, 9, 9, 9, 11 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 1); Assert.IsTrue(Judge(new int[] { 9 }, same)); Assert.IsTrue(noSame.Count == 4); Assert.IsTrue(Judge(new int[] { 5,10, 11 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[4] { 5, 9, 9, 9}; b = new int[5] { 0, 9, 9, 10, 11 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 1); Assert.IsTrue(Judge(new int[] { 9 }, same)); Assert.IsTrue(noSame.Count == 4); Assert.IsTrue(Judge(new int[] { 5,0, 10, 11 }, noSame));
}
private bool Judge(int[] arr, IList<int> list) { bool result=true;
foreach (int item in arr) { if(!list.Contains(item)) { result=false; break; } } return result; }
你们也可以添加测试代码,如何发现有任何的错误,请及时告诉我,谢谢。
public void SearchElement(Int32[] a, Int32[] b, IList<Int32> same, IList<Int32> noSame)
{ if (a == null && b == null) { return; } if (a == null && b != null) { foreach (int item in b) { noSame.Add(item); } return; } if (a != null && b == null) { foreach(int item in a) { noSame.Add(item); } return; }Int32 lena = a.Length; Int32 lenb = b.Length; Int32 ia = 0; Int32 ib = 0; while (ia <= lena - 1 && ib <= lenb - 1) { if (a[ia] < b[ib]) { if (same.Count > 0 && a[ia] == same[same.Count - 1]) { ia++; continue; } noSame.Add(a[ia]); ia++; continue; } if (a[ia] == b[ib]) { if (same.Count >0 && a[ia] != same[same.Count - 1]) { same.Add(a[ia]); ia++; ib++; continue; } if (same.Count == 0 || a[ia] != same[same.Count - 1]) { same.Add(a[ia]); } ia++; ib++; continue; } if(a[ia]>b[ib]) { if ( same.Count>0 && b[ib] != same[same.Count - 1]) { noSame.Add(b[ib]); ib++; continue; } if (same.Count > 0 && b[ib] == same[same.Count - 1]) { ib++; continue; } noSame.Add(b[ib]); ib++; continue; } }
int nowia = ia - 1; while (ia <= lena - 1) { if (nowia < 0) { noSame.Add(a[ia]); } else { if (a[ia] != a[nowia]) { noSame.Add(a[ia]); } } ia++; nowia++; }
int nowib = ib - 1; while (ib <= lenb - 1) { if (nowib < 0) { noSame.Add(b[ib]); } else { if (b[ib] != b[nowib]) { noSame.Add(b[ib]); } } ib++; nowib++; } return; } 测试代码: [TestMethod()] public void SearchElementTest() { LookSameOrNoSameElement target = new LookSameOrNoSameElement(); // TODO: Initialize to an appropriate value int[] a = null; // TODO: Initialize to an appropriate value int[] b = null; // TODO: Initialize to an appropriate value IList<int> same = new List<int>(); // TODO: Initialize to an appropriate value IList<int> noSame = new List<int>(); // TODO: Initialize to an appropriate value
target.SearchElement(a,b,same,noSame); Assert.IsTrue(same.Count == 0); Assert.IsTrue(noSame.Count==0);
same = new List<int>(); noSame = new List<int>(); a = new int[6] { 3,7,10,11,30,40}; b = null; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count==0); Assert.IsTrue(noSame.Count==6); Assert.IsTrue(Judge(a, noSame));
same = new List<int>(); noSame = new List<int>(); a = null; b =new int[5]{4,7,20,30,40}; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 0); Assert.IsTrue(noSame.Count ==5); Assert.IsTrue(Judge(b, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[6] { 3, 7, 10, 11, 30, 40 }; b = new int[5] { 4, 7, 20, 30, 40 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count ==3); Assert.IsTrue(Judge(new int[] { 7,30,40 }, same)); Assert.IsTrue(noSame.Count ==5); Assert.IsTrue(Judge(new int[]{3,4,10,11,20}, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[6] { 3, 7, 10, 11, 30, 40 }; b = new int[6] { 3, 7, 20, 30, 40,100 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count ==4); Assert.IsTrue(Judge(new int[] { 3,7, 30, 40 }, same)); Assert.IsTrue(noSame.Count ==4); Assert.IsTrue(Judge(new int[] { 10, 11, 20,100 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[1] { 0 }; b = new int[1] { 0}; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count ==1); Assert.IsTrue(Judge(new int[] { 0 }, same)); Assert.IsTrue(noSame.Count == 0);
same = new List<int>(); noSame = new List<int>(); a = new int[2] { 0 ,9}; b = new int[2] { 0,9 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count ==2); Assert.IsTrue(Judge(new int[] { 0,9 }, same)); Assert.IsTrue(noSame.Count == 0);
same = new List<int>(); noSame = new List<int>(); a = new int[2] { 0, 9 }; b = new int[2] { 10,20}; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count ==0); Assert.IsTrue(noSame.Count == 4); Assert.IsTrue(Judge(new int[4]{0,9,10,20},noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[6] { 3, 7, 7, 11, 30, 40 }; b = new int[5] { 4, 7, 20, 30, 40 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 3); Assert.IsTrue(Judge(new int[] { 7, 30, 40 }, same)); Assert.IsTrue(noSame.Count == 4); Assert.IsTrue(Judge(new int[] { 3, 4, 11, 20 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[2] {0,9}; b = new int[3] { 0,9,9 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 2); Assert.IsTrue(Judge(new int[] { 0,9 }, same)); Assert.IsTrue(noSame.Count == 0);
same = new List<int>(); noSame = new List<int>(); a = new int[2] { 0, 9 }; b = new int[4] { 0, 9, 10,10}; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 2); Assert.IsTrue(Judge(new int[] { 0, 9 }, same)); Assert.IsTrue(noSame.Count ==1); Assert.IsTrue(Judge(new int[] { 10 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[2] { 0, 9 }; b = new int[5] { 0, 9, 10, 10,11 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 2); Assert.IsTrue(Judge(new int[] { 0, 9 }, same)); Assert.IsTrue(noSame.Count == 2); Assert.IsTrue(Judge(new int[] { 10,11 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[4] { 0, 9 ,9,10}; b = new int[5] { 0, 9, 9,9, 11 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 2); Assert.IsTrue(Judge(new int[] { 0, 9 }, same)); Assert.IsTrue(noSame.Count == 2); Assert.IsTrue(Judge(new int[] { 10, 11 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[4] { 5, 9, 9, 10 }; b = new int[5] { 0, 9, 9, 9, 11 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 1); Assert.IsTrue(Judge(new int[] { 9 }, same)); Assert.IsTrue(noSame.Count == 4); Assert.IsTrue(Judge(new int[] { 5,10, 11 }, noSame));
same = new List<int>(); noSame = new List<int>(); a = new int[4] { 5, 9, 9, 9}; b = new int[5] { 0, 9, 9, 10, 11 }; target.SearchElement(a, b, same, noSame); Assert.IsTrue(same.Count == 1); Assert.IsTrue(Judge(new int[] { 9 }, same)); Assert.IsTrue(noSame.Count == 4); Assert.IsTrue(Judge(new int[] { 5,0, 10, 11 }, noSame));
}
private bool Judge(int[] arr, IList<int> list) { bool result=true;
foreach (int item in arr) { if(!list.Contains(item)) { result=false; break; } } return result; }
相关阅读 更多 +