来接分，顺便留下你的算法【求任意长度的两个正整数数组中 重复数字的个数】

Question

假设有两个整数数组A、B，已知这两个数组长度任意，并且每个数组中的数字都是惟一的。
要求用较快的算法求解A和B中重复的数字个数。

Answer 1

[code]
            var n1 = new[] { 1,2,3,4,5,6,7,8,9,10 };
            var n2 = new[] { 0,2,4,6,8 };
            var count=0;
            foreach (var i in n1.Intersect(n2))
                count++;
            Console.Write(count);
            Console.ReadLine();
[/code]

Answer 2

            var n1 = new[] { 1,2,3,4,5,6,7,8,9,10 };
            var n2 = new[] { 0,2,4,6,8 };
            var count=0;
            foreach (var i in n1.Intersect(n2))
                count++;
            Console.Write(count);
            Console.ReadLine();

Answer 3

更正一下，更简单的办法是直接用Intersect.Count()方法：            var n1 = new[] { 1,2,3,4,5,6,7,8,9,10 };
            var n2 = new[] { 0,2,4,6,8 };
            Console.Write(n1.Intersect(n2).Count());这个是c#3.0的特性

Answer 4

用一个 HashSet 装入数组 A 的值，然后再循环 B，判断 B 中的数字是否在 HashSet 中，若在，则加入重复数字的列表，这是否会快一些呢？

Answer 5

看看我写得对不对
int[] Array1={1,2,3,4,5,6}
int[] Array2={11,2,3,4,5,6,7,8}
int len1=Array1.length
int len2=Array2.length
list<int> a=new list<int>
for (int i=0,i<len1,i++)
{
 a.add(Array1(i))}
  for (int j=0,j<len2,j++)
  {
   if (!a.Contains(Array2(j)))
   {
   a.add(Array2(j))
    }
  }
int len3=a.lengthreturn len1+len2-len3

Answer 6

list<int> a=new list<int>()

Answer 7

int[m] m1= new int{a1,a2,...,am};
int[n] m2= new int{b1,b2,...,bn};
int iEqualCount = 0 ;
for(int i =0;i<m;i++)
{
int iValue = m1[i];
for(int j=0;j<n;j++)
{
if(ivalue==m2[j])
iEqualCount ++;
}
}

Answer 8

把二个数组合成一个数组,然后排序,然后比较A[i]和A[i+1]是否相同,这样就行了.

Answer 9

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;namespace DemoInrtArray
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 0;
            int[] aArray = new int[] { 1, 2, 3, 45, 6, 7, 890 };
            int[] bArray = new int[] { 10, 20, 3, 6, 890, 100, 30, 1 };
            int lenA = aArray.Length;
            int lenB = bArray.Length;
            List<int> cpArray = new List<int>();
            if (lenA > lenB)
            {
                foreach (int a in aArray)
                {
                    cpArray.Add(a);
                }
                foreach (int b in bArray)
                {
                    if (cpArray.Contains(b))
                    {
                        count++;
                        cpArray.Remove(b);
                    }
                }
            }
            else
            {
                foreach (int b in bArray)
                {
                    cpArray.Add(b);
                }
                foreach (int a in aArray)
                {
                    if (cpArray.Contains(a))
                    {
                        count++;
                        cpArray.Remove(a);
                    }
                }
            }
            Console.Write(count);
            Console.ReadLine();
        }
    }
}考虑到Contains的方法实际上也是遍历进行判断，所以Remove了一下。
感觉应该有比List合适的集合，这方面接触的不多。如果2个数组大小很小的话以上代码可能只会降低效率，不过既然是长度不定的话，我还是这么写了
有什么需要改进的地方请指出

Answer 10

14楼的算法using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;namespace DemoInrtArray
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 0;
            int[] aArray = new int[] { 1, 2, 3, 45, 6, 7, 890 };
            int[] bArray = new int[] { 10, 20, 3, 6, 890, 100, 30, 1 };
            int maxLength = aArray.Length + bArray.Length;
            int[] cArray = new int[maxLength];
            aArray.CopyTo(cArray, 0);
            bArray.CopyTo(cArray, aArray.Length);            int temp = 0;
            for (int i = 0; i < cArray.Length - 1; i++)
            {
                for (int j = 0; j < cArray.Length - i - 1; j++)
                {
                    if (cArray[j] > cArray[j + 1])
                    {
                        temp = cArray[j];
                        cArray[j] = cArray[j + 1];
                        cArray[j + 1] = temp;
                    }
                }
            }            for (int i = 0; i < cArray.Length; i++)
            {
                if (cArray[i] == cArray[i + 1])
                {
                    count++;
                    i++;
                }
            }
            Console.Write(count);
            Console.ReadLine();           
        }
    }
}

Answer 11

支持6楼的想法。Intersect()方法：返回包含组成两个序列交集的元素的序列。
 
用这个代码最简单。
Intersect方法机制，先循环第一个数组，获得该数组中的所有非重复元素，
然后循环第二个数组，找到那些同时出现在两个数组中的元素。需要2次循环，虽然也有一次循环的就能解决问题的办法，但这个方法让代码量大减。

Answer 12

我在想前几天一个使用map的程序

Answer 13

是不是可以使用类似STL的泛型算法来解决。
假设 roster1 和 roster2 是两个存放名字的 list 对象，可使用 find_first_of 统计有多少个名字同时出现在这两个列表中：     // program for illustration purposes only:
     // there are much faster ways to solve this problem
     size_t cnt = 0;
     list<string>::iterator it = roster1.begin();
     // look in roster1 for any name also in roster2
     while   ((it = find_first_of(it, roster1.end(),
                  roster2.begin(), roster2.end()))
                     != roster1.end()) {
        ++cnt;
        // we got a match, increment it to look in the rest of roster1
        ++it;
     }
     cout << "Found " << cnt
          << " names on both rosters" << endl;

Answer 14

楼主说用算法，而不是c#的特性。只能是两层循环吧
int Count=0;
for (int i=0;i<a.lenght;i++)
{
  for(int j=0;j<b.lenght;j++)
 {
     if(a[i]==b[j])
     {
       Count+=1;
       //最好是移除它这样下次就不用在循环了可以减少循环次数。
       b.remove(b[i])
    }
 }
}

Answer 15

先把数组值赋值给List泛型，再排序，再相互比较

Answer 16

int[] Array1={1,2,3,4,5,6}；
int[] Array2={11,2,3,4,5,6,7,8}；
int num = 0;
int len1=Array1.length；
int len2=Array2.length；
string test = string.empty；
for (int i=0,i<len2,i++)
{test +=  Array2[i];
}
for(int i=0;i<len1,i++)
{
if(Array1[i].tostring().index(text)> 0)
   num++;
}

Answer 17

改成indexof

Answer 18

我觉得：
1.楼主要的是算法，而不是方法、涵数，所以6楼的答案不是最佳。
2.大家都没有考虑到数组长度的问题，如果A、B数组的长度有几十万，几百万呢？
3.很多人说先排序，但有没有想过排序工作本身也消耗资源。
4.用list和数组拼接的方法，如果数据量过大，系统不但要承受几百万次的循环，还要产生一个几百万条记录的list
5.所以我觉得34楼这样的答案比较接近楼主的要求。其实就是简单的两次循环，关键在于，34楼有想到“最好是移除它这样下次就不用在循环了可以减少循环次数”。因为楼主有强调：“每个数组中的数字都是惟一的”，所以当在B数组找到相同的数字后，完全可以把其删除，下一次的遍历就不会判断到，B数组在判断的过程中会越来越少，b.lenght会越来越小，实际循环次数将会比其它方法的要少。当数据量达到百万级的时候，效果就非常明显了。

Answer 19

Intersect()，Contains()，这些都是方法，不是算法，你们把工作全扔给了引擎。14楼的想法也是无视的数组长度和排序所耗资源。16楼也有删除重复记录，缩小数组，减少循环的思路，而且还争对AB数组大小来做不同的循环。美中不除还是用到了list，如果A有500万条，B有500万条，恭喜你，获得了一个1000万条的list。

Answer 20

有 code=C/C++ 的不？？
关注。

Answer 21

用六楼的方法吧,一是.net自带,二是带码量少,如果不是数据量巨大,会有很大性能上的影响,作为编码人员来说,能少写一行是一行,只要微软提供了,就用现成的,开发周期更重要.

Answer 22

使用双套循环不如将数组1放入二叉树 在遍历数组二。复杂度虽然一样，但是实际的查询效率会高很多。另外对原始数组是否排序没有要求。
CODE：    //建立二叉树 
    public class Node
    {
        public int data;
        public Node left;
        public Node right;
        public Node()
        {
            data = -1;
        }
        
        //添加Node
        public void AddNode(int value)
        {
            if (data == -1)
            {
                data = value;
                return;
            }
            if (value < data)
            {
                if (left == null)
                {
                    left = new Node();
                }
                left.AddNode(value);
            }
            else
            {
                if (right == null)
                {
                    right = new Node();
                }
                right.AddNode(value);
            }
        }       //在二叉数里查询Node是否存在
        public bool SelectNode(int value)
        {
            //总共查询次数
            Form1.totalCount++;       
            if (value == data)
            {
                return true;
            }
            else
            {
                if (value < data)
                {
                    if (left == null)
                    {
                        return false;
                    }
                    return left.SelectNode(value);
                }
                else
                {
                    if (right == null)
                    {
                        return false;
                    }
                    return right.SelectNode(value);
                }
            }
        }
    } 
 
        // 程序主体 ------------ 
        private void button2_Click(object sender, EventArgs e)
        {
            int[] a = { 9, 3, 2, 1, 7, 5, 8, 4, 6 };
            int[] b = { 6, 3, 0, 11 ,1,13,2};
            Node n = new Node();
   
            for (int i = 0; i < a.Length; i++)
            {
                n.AddNode(a[i]);
            }            int count = 0;
            for (int j = 0; j < b.Length; j++)
            {
                if (n.SelectNode(b[j]))
                {
                    count++;
                }
            }            //显示相同个数
            MessageBox.Show(count.ToString());
        }

Answer 23

其实简单和复杂并不是看现有代码的量和效率吧
比如6#说的Intersect.Count()方法，其实我们并没有考虑这个方法内部的代码是如何进行的啊，如果根据版本升级来考虑问题，那我们自己也可以写个带有2个数组参数的方法，然后直接调用这个自己的方法那不是只有一步？

Answer 24

我感觉可以用背包那种方法做
任意数组
所以长度是能比较的
我的设想大概是这样
foreach（int i in 长数组）{
    ....//正体为递归中用i和短数组逐个比较，如果相同count++；
     //最后输出count
}

Answer 25

            var n1 = new[] { 1,2,3,4,5,6,7,8,9,10 }; 
            var n2 = new[] { 0,2,4,6,8 }; 
            Console.Write(n1.Intersect(n2).Count()); 水么？

Answer 26

这是一道算法复杂性的问题吧，咋个都在讨论.Net的机制问题去了呢

Answer 27

var n1 = new[] { 1,2,3,4,5,6,7,8,9,10 };
var n2 = new[] { 0,2,4,6,8 };
Console.Write(n1.Intersect(n2).Count()); 这叫算法??完全没有移植性了..

Answer 28

这个是linq里面的成员吧走IEnumerable接口的？？？
写的很简单，不知性能如何
给做个实验，用它和最简单的双循环做对比

Answer 29

我的思路，不成熟，大家探讨。单纯讨论算法，既然lz要效率最高的，那就用空间换时间
已知两个数组和每个数组的长度，已知数组没有重复的数字
假设
A[]={1,2,3,4,5,6,7,8,9,10}
A.Length=10
B[]={2,0,8,4,6}
B.Length=51.比较两个数组长度，选其中较短的一个数组，建立其有序数组
C[]={0,2,4,6,8}2.遍历较长的数组数据，和C中的数据比较，如果找到计数器++，从C中删除这个数据；如果没找到继续下一个
既然C已经是有序数组，每次比较就无需从头索引了，按照数组中间位置取值比大小的方法，效率应该是可以高很多

Answer 30

楼上的大部分人是高级语言用的太多了吧？
这是一道算法题！应该先排序 为 Nlog(N）复杂度
然后依次对第二个数组中的数用二分查找
二分查找的min会逐渐往后移
复杂度应该也是 Nlog(N）所以此算法的复杂度为 Nlog(N）

Answer 31

假设有两个整数数组A、B，已知这两个数组长度任意，并且每个数组中的数字都是惟一的。 
要求用较快的算法求解A和B中重复的数字个数。
每组每个数字都是唯一的。
其实排序的过程中。就可以获取A[i]和A[i+1]的大小。用个变量保存下。排序结束，重复的次数就出来了。
重复的次数必定就是A和B中重复的数字个数！

Answer 32

int[m] m1= new int{a1,a2,...,am};
int[n] m2= new int{b1,b2,...,bn};
int iEqualCount = 0 ;
for(int i =0;i<m;i++)
{
int iValue = m1[i];
for(int j=0;j<n;j++)
{
if(ivalue==m2[j])
iEqualCount ++;
}
} 
 

Answer 33

就是位映射方法（Bitmap)，我想这是效率最高的。

Answer 34

用linq一条就可以搞定，但不知道效率如何；

Answer 35

用Hashtable, 遍历小数组建立此table作为键值,然后遍历大数组,在hashtable中找到对应键.加1.2.0环境下这是最省力效率也不算低的方法了.

Answer 36

using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {        
            public void calculate()
            {
                int[] arr1 = new int[5] { 1, 2, 7, 4, 5 };
                int[] arr2 = new int[3] { 1, 2, 3 };
                int count = 0;
                for (int i = 0; i < arr1.Length; i++)
                {
                    for (int j = 0; j < arr2.Length; j++)
                    {
                        if (arr1[i] == arr2[j])
                        {
                            count++;
                        }
                    }
                }
                Console.WriteLine("arr1 中与 arr2 相等的数有 " + count+" 个");
            }        
        static void Main(string[] args)
        {
            Program pro = new Program();
            pro.calculate();
            Console.ReadLine();
        }
    }
}