查找交集算法，有一点难度（欢迎大家讨论）

using System.Text;...... [STAThread]
static void Main(string[] args)
{
string[] ary=new string[3];
ary[0]="0,1,5,7,12,15,18,20";
ary[1]="0,1,5,8,13,15,19,20";
ary[2]="1,5,6,12,14,15,18,20"; StringBuilder strResult=new StringBuilder(); string[] strs=ary[0].Split(new Char[]{','});
string[] strs1=ary[1].Split(new Char[]{','});
string[] strs2=ary[2].Split(new Char[]{','}); foreach(string st in strs)
{
foreach(string st1 in strs1)
{
if(st==st1)
{
foreach(string st2 in strs2)
{
if(st==st2)
{

strResult.Append(st);
strResult.Append(",");
}
}
}
}
} Console.WriteLine(strResult);
Console.ReadLine();
} :)

stringBuilder s=new StringBuilder("");
for(i=0,i<ary[0].Length,i++)
{
   if (ary[1].IndexOf(ary[0][i])>=0)
   if (ary[2].IndexOf(ary[0][i])>=0)
      s.Append (ary[0][i]);
}

0-20循环，在三个数组中查找，只要循环一遍。t=O(n)

chNET(有神论者) 方法是可以的，有你的分
但是，你的遍历的次数太多了
效率可不是很好
有更好的么？

想错了
string[] ary=new string[3];
ary[0]="0,1,5,7,12,15,18,20";
ary[1]="0,1,5,8,13,15,19,20";
ary[2]="1,5,6,12,14,15,18,20";
StringBuilder strResult=new StringBuilder();
string[] strs=ary[0].Split(new Char[]{','});
string[] strs1=ary[1].Split(new Char[]{','});
string[] strs2=ary[2].Split(new Char[]{','});
ArrayList a2=new ArrayList();
ArrayList a3=new ArrayList();
foreach(string s in strs2)
{
   a2.Add(s);
}
foreach(string s ing strs3)
{
   a3.Add(s);
}
foreach(string s in strs1)
{
    if (a2.Contains(s))
       if  (a2.Contains(s))
            strResult.Append (s);}

写错了
string[] ary=new string[3];
ary[0]="0,1,5,7,12,15,18,20";
ary[1]="0,1,5,8,13,15,19,20";
ary[2]="1,5,6,12,14,15,18,20";
StringBuilder strResult=new StringBuilder();
string[] strs1=ary[0].Split(new Char[]{','});
string[] strs2=ary[1].Split(new Char[]{','});
string[] strs3=ary[2].Split(new Char[]{','});
ArrayList a2=new ArrayList();
ArrayList a3=new ArrayList();
foreach(string s in strs2)
{
   a2.Add(s);
}
foreach(string s ing strs3)
{
   a3.Add(s);
}
foreach(string s in strs1)
{
    if (a2.Contains(s))
       if  (a2.Contains(s))
            strResult.Append (s);}

strResult 返回结果应该是"1,5,15,20" 才对吧？题目出错了？

呵呵，瞧瞧版主的：string[] c=ary[0].Split(',');
string strResult = "";for(int i=0; i<c.Length;i++){
if ((","+ary[1]+",").IndexOf(","+c[i]+",")>=0 && (","+ary[2]+",").IndexOf(","+c[i]+",")>=0) {
strResult += c[i] + ",";
}
}MessageBox.Show(strResult.Remove(strResult.Length-1,1));正宗的答案吧，呵呵

string[] ary=new string[3];
ary[0]="0,1,5,7,12,15,18,20";
ary[1]="0,1,5,8,13,15,19,20";
ary[2]="1,5,6,12,14,15,18,20"; string[] strs1=ary[0].Split(new Char[]{','});
string[] strs2=ary[1].Split(new Char[]{','});
string[] strs3=ary[2].Split(new Char[]{','}); ArrayList arrResult1=new ArrayList();
ArrayList arrResult2=new ArrayList();
ArrayList arrResult3=new ArrayList();
for(int i=0;i<strs1.Length;i++)
{
for(int ii=0;ii<strs2.Length;ii++)
{
if(strs1[i]==strs2[ii])
arrResult1.Add(strs1[i]);
}
for(int iii=0;iii<strs3.Length;iii++)
{
if(strs1[i]==strs3[iii])
arrResult2.Add(strs1[i]);
}
} switch(arrResult1.Count>arrResult2.Count)
{
case true:
{
for(int j=0;j<arrResult2.Count;j++)
{
int index1=arrResult1.IndexOf(arrResult2[j].ToString());
if(index1>=0)
arrResult3.Add(arrResult1[index1].ToString());
}
break;
}
case false:
{
for(int k=0;k<arrResult1.Count;k++)
{
int index2=arrResult2.IndexOf(arrResult1[k].ToString());
if(index2>=0)
arrResult3.Add(arrResult2[index2].ToString());
}
break;
}
} for(int x=0;x<arrResult3.Count;x++)
{
Console.WriteLine(arrResult3[x].ToString());
}

答案的确像"ArLi2003(阿利风雨中的无爪飞龙) "所说的
"1,5,15,20"

感谢大家的关心，其实我们正在逼近完美结果
我来评论一下：
1、chNET(有神论者) 方法是可以的，但是，遍历的次数太多了
2、 ljj77(小妖) 同志结构容易理解，但是效率比较低，速度也不高
3、qimini(循序渐进)同志的代码太长了，效率最低
4、斑竹是目前最好的方法，但是还有可以改善的地方我提供一下思路：
1、System.Array.Sort()可以排序数组，所以开始的时候最好拆分成数组
2、数组有一个二分法查找的函数，效率比较好
3、数据是有规律的，比如ary[0]中的0，和ary[1]比较的时候如果第一个就是，我们
就应该在ary[1]不再查询遍历了，而应该遍历ary[2]；如果ary[0]中的0在ary[1]中没有
则本次遍历应该终止，进行ary[0]中的1的比较

刚才写到一半半停电了，晕。。这个问题如果从你的角度去看其实是矛盾的，性能和资源往往是反比，我上面的例子是从资源出发的，毕竟现在的CPU越来越快了，但资源越来越有限如果数据集很大，要求高效的方法，应该：比如 a[0] = "1,4,20";那么就建立一个 bool[] b0 = new bool[20]; 然后根据a[0] 各元素置 b0[] 对应元素为true，比如：b0[1] = true;
b0[4] = true;
b0[20] = true;在a[0] 里没有的，也就是未付值的都是false，其它比如b1 也这样付值然后判断如下：if (b0[i] && b1[i] && b2[i]){
returnvalue += i.tostring();
}因为&& 是记忆判断，所以前面哪个不匹配，后面就不会再计算，而bool 的& 计算是最快的，速度永远是：bool->int->char->string这样对付大的数据集的性能是最快的，但资源也比了一些

贴出代码吧，省的口水，速度最快的方法：private static string GetPoc (string str1, string str2, string str3,int MaxOf){
string[] s1 = str1.Split(',');
string[] s2 = str2.Split(',');
string[] s3 = str3.Split(','); bool[] b1 = new bool[MaxOf + 1],b2 = new bool[MaxOf + 1],b3 = new bool[MaxOf + 1]; for (int i=0; i<s1.Length;i++) { //不用多次遍历，一次搞定
b1[int.Parse(s1[i])] =true;
b2[int.Parse(s2[i])] =true;
b3[int.Parse(s3[i])] =true;
} string strResult = null; // 搜索交集
for (int i=0; i<b1.Length; i++) {
if (b1[i] && b2[i] && b3[i]){
strResult += i.ToString() + ",";
}
} return strResult.Remove(strResult.Length-1,1);
}调用：GetPoc(ary[0],ary[1],ary[2],20/*这是指定元素最大可能，楼主的是20*/);
这样就算有1000^1000 个也不怕，快的很哩，不必遍历，不必排序，不必指针
我什么时候面试碰上这种问题就好了，可惜连要都没人要。。

string[] ary = new string[3];
ary[0] = "0,1,5,7,12,15,18,20";
ary[1] = "0,1,5,8,13,15,19,20";
ary[2] = "1,5,6,12,14,15,18,20";
string middleReslut = "";
string stringResult = ""; ary[1] = "," + ary [1] + ",";
ary[2] = "," + ary [2] + ","; string[] ary0 = ary[0].Split(','); for (int i = 0 ; i < ary0.Length ; i++)
{
if (ary[1].IndexOf("," + ary0[i] + ",") != -1)
{
middleReslut += ary0[i] + ",";
}
} string[] aryM = middleReslut.Split(','); for (int j = 0 ; j < aryM.Length ; j++)
{
if (ary[2].IndexOf("," + aryM[j] + ",") != -1)
{
stringResult += aryM[j] + ",";
}
} if (stringResult.Length > 0)
{
stringResult = stringResult.Substring(0,stringResult.Length - 1);
} MessageBox.Show(stringResult);//经测试用时0.1718秒
//版主的用时0.2987秒

我的第一个indexof 那个是对付小数据集
下面一个是对付大数据集，如果数据集是1000*1000 那用indexof 是肯定不现实的

ary[2] = "1,5,6,12,14,15,18,20"; //如果这里有10000 个元素，还用indexof？呵呵

Arli2003的方法不安全，如果我其中一个字符串的构成是这样的：
str1 =  "1," + int.MaxValue.ToString();
str2 =  "1," + int.MinValue.ToString();一个会产生上溢出（内存不足），另外一个会产生下溢出。如果是我做的话就用两个HashTable做。private static string GetPoc (string str1, string str2, string str3)
{
    string[] ss;
    HashTable ht1 = new HashTable();
    HashTable ht2 = new HashTable();    str1 += "," + str2 + "," + str3;
    str2 = "";
    ss = str1.Split(',');
    for (int i=0; i<s1.Length;i++)
    {
        str3 = s1[i];
        if (ht1.Contains(str3)
            if (ht2.Contain(str3)
                str2 += str3 + ",";
            else
                ht2.Add(str3, str3);
        else
            ht1.Add(str3, str3);
    }
    return str2;
}
估计速度不会太快，但是在大数据量时非常有优势，速度跟ArLi2003后面的方法相比不好说，但是应该相差不大，如果数据比较稀疏的话优势应该非常明显，主要是ArLi2003的方法需要分配大数组空间，可能比较耗时。此外就是我提到的极端情况下可能会出现上下溢出的问题，不安全。如果是我，我不会在小数据量上面计较速度问题，就算是大数据量，也应当首要考虑绝对稳定可靠不会出现无法处理极端情况的例子。大家觉得呢？其实速度应当不算最快的，此外有一个可以加速的地方就是，str2 += str3 + ",";的地方，此处应当用StringBuilder来处理，速度绝对可以大幅提高！
至于全面有人提示的Array.Sort();我看还是免了，string的排序非常耗时，如果先转换成数值可能也没有多大改善。

呵呵，这个答案我可是有研究过的哟：1，说我的不安全，元素的大小会超过int 的最大值：2147483647？不会吧。。呵呵，就算可能那可以使用double2，在搜索方面绝对没有比我的 bool & bool 更快了。。用.Contains是最慢的string 比较，速度是bool->int->char->string 哟3，申请空间只是内存映射速度上绝对不会占的，呵呵10000 个元素申请一版10000大小的堆栈会慢？就算10000000 也绝对比计算快，你要知道，我的要申请内存空间，你们不管用什么方法都得申请空间，不是吗？简单的说，比如楼上的 str1 += "," + str2 + "," + str3; 那么str1 已经和我一样申请了空间，我的要申请10000，你的str1 也一样要申请10000，我的又不用计算，何乐不为？4，用sort 是不可能，太慢，用哈希表还不如用sortlist期待高见..

既然大家毫秒必争，我再说两个可以改进的地方： 1、如果要用比较运算符，就用 Equals() 方法，而不要用 == 2、楼上几位兄弟这样处理 strResult ：
        string strResult=null;
    建议：
        StringBuilder strResult=new StringBuilder();
    理由：
        string 必须分配一个新的字符串并复制字符
        StringBuilder 可以在相同的内存空间中执行这些操作...

        在数据量很大时，优势明显(如：交集元素为 1000 个) 期待高见.. :)

TO： chNET(有神论者)你的第1点好象理解不对哦，下面摘自MSDN
=======================================
返回值
如果 a 的值与 b 的值相同，则为 true；否则为 false备注
使用 Equals 方法实现此运算符，这意味着就引用相等和值相等的组合对比较数进行测试。该比较区分大小写。
========================================

参考MSDN的String类的静态方法CompareTo可以直接比较两个字符串中的值。以下摘自MSDN：==================================================================
将此实例与指定的 String 对象进行比较。[C#]
[Serializable]
public int CompareTo(
   string strB
);
[参数]strB
一个 String。
返回值
一个 32 位有符号整数，指示两个比较数之间的词法关系。值条件
小于零此实例小于 value。
零此实例等于 value。
大于零此实例大于 value。
-或-value 为空引用（Visual Basic 中为 Nothing）。备注
根据定义，任何 String（包括空字符串）的比较结果都大于空引用；两个空引用的比较结果为相等。============================================================================

前面没有看清题目（以为只要算法），下面是我改进的代码（算法没有变）：                   string[] ary=new string[3];
ary[0]="0,1,5,7,12,15,18,20";
ary[1]="0,1,5,8,13,15,19,20";
ary[2]="1,5,6,12,14,15,18,20";
//**********其实个人觉得下面这段代码极其影响效率，希望能抛砖引玉引起各位高手关注
string[] strs1=ary[0].Split(new Char[]{','});
string[] strs2=ary[1].Split(new Char[]{','});
string[] strs3=ary[2].Split(new Char[]{','});
//***********
string arrResult=null; for(int i=0;i<strs1.Length;i++)
{
int pos1=-1;
int pos2=-2;
for(int ii=0;ii<strs2.Length;ii++)
{
if(strs1[i].CompareTo(strs2[ii])==0)
pos1=i;
}
for(int iii=0;iii<strs3.Length;iii++)
{
if(strs1[i].CompareTo(strs3[iii])==0)
pos2=i;
}
if(pos1==pos2)
{
if(strResult==null)
   strResult=strs1[i];
else
   strResult=strResult+","+strs1[i];
}
}

呵呵，小数据集用string[] c=ary[0].Split(',');
string strResult = "";for(int i=0; i<c.Length;i++){
if ((","+ary[1]+",").IndexOf(","+c[i]+",")>=0 && (","+ary[2]+",").IndexOf(","+c[i]+",")>=0) {
strResult += c[i] + ",";
}
}MessageBox.Show(strResult.Remove(strResult.Length-1,1));上面这个是最精简的，大数据集用：private static string GetPoc (string str1, string str2, string str3,int MaxOf){
//允许不定义元素大小
if (MaxOf==0) MaxOf = 65535; string[] s1 = str1.Split(',');
string[] s2 = str2.Split(',');
string[] s3 = str3.Split(','); //允许不对称交集，找到出三个数组最大上限的一组
int upOf = s1.Length>s2.Length ? s1.Length > s3.Length ? s1.Length : s3.Length :s2.Length; bool[] b1 = new bool[MaxOf + 1],b2 = new bool[MaxOf + 1],b3 = new bool[MaxOf + 1]; for (int i=0; i<upOf;i++) { //不用多次遍历，一次搞定
if (i<s1.Length) b1[int.Parse(s1[i])] =true;
if (i<s2.Length) b2[int.Parse(s2[i])] =true;
if (i<s3.Length) b3[int.Parse(s3[i])] =true;
} string strResult = null; // 搜索交集
for (int i=0; i<b1.Length; i++) {
if (b1[i] && b2[i] && b3[i]){
strResult += i.ToString() + ",";
}
} return strResult.Remove(strResult.Length-1,1);
}哪位不信，自己生成10000*3组来测试一下，没有比bool 更快了，你们怎么老是打string 的主意？就算是 CompareTo 或者 == 都是按位比较，一个string 有多少位？而我的bool 只有一位就是1和0 怎么可能有更快？不信的把你的方法写成GetPoc 子程序，自己用下面这个试一下：string[] ary=new string[3];
System.Random rnd = new Random();
int min=0, max = 10000;
for (int i=0; i<max; i++) {
ary[0] += (rnd.Next(min,max)).ToString() + ",";
ary[1] += (rnd.Next(min,max)).ToString() + ",";
ary[2] += (rnd.Next(min,max)).ToString() + ",";
}
ary[0] = ary[0].Remove(ary[0].Length-1,1);
ary[1] = ary[1].Remove(ary[1].Length-1,1);
ary[2] = ary[2].Remove(ary[2].Length-1,1);MessageBox.Show("生成完成，开始计时");
DateTime dt = DateTime.Now;GetPoc(ary[0],ary[1],ary[2],max); //开始处理double len = (DateTime.Now - dt).TotalSeconds;
MessageBox.Show(len.ToString());我的大数据集处理还有些优点：
1，容错性，允许交集重复
2，无任何字符比较操作，无排序，无遍历
3，允许不对称数据集但它的new byte 要多申请一些可能的空空间，但在1M以下都几乎是可以忽略。。
数据结构偶很菜，但在数据处理上可做过不少年了，呵呵。。
吵架就是提高，期待有更好的方法

To ArLi2003：   不会吧！你连这个这么大的漏洞都没看出来？我说的问题不在于是int还是double，问题是你申请了三个bool数组。bool的长度是4个字节，你的这三个bool数组是以需要对比的那几个字符串当中最大的那一个为上界进行定义的。看看我的特例：str1 =  "1," + int.MaxValue.ToString();在你代码当中：
bool[] b1 = new bool[MaxOf + 1],b2 = new bool[MaxOf + 1],b3 = new bool[MaxOf + 1];那我问你，这个MaxOf是不是等于2147483647？MaxOf+1是不是等于2147483648，姑且不论这个2147483648是否会超出数组定义的界限，但是你有没有想过这需要多少的内存？2G*4B = 8GB，这只是其中一个数组，还有两个呢！试问你的机子承受得起吗？
你说的内存映射是不对的，不信你可以试一下，申请一个2G个元素的数组，如果你嫌太大了，你可以试一下申请100M个元素的数组试一下。也许太特殊了，没关系，那么负数呢？负数你的方法怎么解决？b1[-1] = true 吗？浮点呢？b2[3.4] = true　吗？你说用sortlist，不敢认同，hash在任何时候都会比sort快，这就是为什么编译器都是使用hash而不是sort加二分查找。尤其是在大量添加新元素的时候，hash会表现得比其他方法更加快（当然，前提是能够迅速查找）。下面是各个方式的空间复杂度表：（都是最理想情况下）              数组         排序数组（链表）         哈希表
添加          O(1)         O(Log2(N))（快速排序）    O(1)
访问          O(N)         O(Log2(N))（二分查找）    O(1)
删除          O(N/2)       O(Log2(N))（再排序）      O(1)实际上哈希的表现不可能这么好，他的表现根冲突有关。不过如果设计的好，已有的元素达到总容量的50%时都能够非常接近O(1)，就算设计的比较糟糕，只要已由元素比总容量的30%小就也能够接近O(1)，比如说O(2)、O(3)之类的。如果N=1000，相信不用说都能够看出来hash的优势了吧？

To chNET(有神论者) :
第一点不敢认同，实际上区别并不是非常的大，没必要为了1%的性能破坏可读性。不要告诉我用于军工什么的，如果那样的话从硬件着手提升个4%都不是非常难，最简单的加个水冷然后超频……第二点认同，我之前也提到了，不过我觉得关键的思路不在这里，能够用StringBuilder的人应该不少，但是这个不是思路的问题。（不过在这个贴子里面好象还是我先提出来的吧？嗬嗬！）To ArLi2003(阿利风雨中的无爪飞龙) :我的大数据集处理还有些优点：
1，容错性，允许交集重复
—— ：）偶的不行，不过偶觉得那没有什么意义，如果一定要的话，稍微该动一下就OK了。（分三个循环做）
2，无任何字符比较操作，无排序，无遍历
—— ：）偶得也没有啊。（严格来说应当是没有O(N)以外的……）
不过侬的似乎要求得到字符串中的最大数啊，所以总体复杂度实际上是O(3N)，偶的是O(2N)。
3，允许不对称数据集
—— ：）偶也可以啊。但它的new byte 要多申请一些可能的空空间，但在1M以下都几乎是可以忽略。。
—— 是new bool啦！四倍于new byte啊！如果字符串里面含有100000000这个数字就够你受的了
数据结构偶很菜，但在数据处理上可做过不少年了，呵呵。。
吵架就是提高，期待有更好的方法

using System;
using System.Collections;
using System.Text;namespace ConsoleApplication1
{
class Class1
{
[STAThread]
static void Main(string[] args)
{
string[] ary=new string[3];
ary[0]="0,1,5,7,12,15,18,20";
ary[1]="0,1,5,8,13,15,19,20";
ary[2]="1,5,6,12,14,15,18,20"; ArrayList al=new ArrayList(ary[0].Split(",".ToCharArray()));
for(int k=1;k<ary.Length;k++)
{
string str=","+ary[k]+",";
for(int i=0;i<al.Count;i++)
{
if(str.IndexOf(","+al[i].ToString()+",")==-1)
{
al.RemoveAt(i);
continue;
}
}
} StringBuilder sb=new StringBuilder();
foreach(string s in al)
{
if(sb.Length!=0)sb.Append(",");
sb.Append(s);
}
Console.WriteLine(sb);
}
}
}

1，我说过了，资源和性能是反比，如果要资源，我第一个方法就是最节省的，在循环内就已经重用资源了。2，你所说的不少东西都是很偏激的，比如int.MaxValue 出现的情况可能的话，那就说明将可能有2G个元素？就按你说的，做最坏的打算，str1、2、3 全是int.MaxValue 也就是 2G 个不同大小的元素，用你的方法试试：ht1.Add(str3, str3);
ht2.Add(str3, str3);这就表示要占4倍的元素空间，再加上你的：str1 += "," + str2 + "," + str3; 这个str1 又要占2倍的空间，总共是2G*6=12G，这是资源，再帮你做最好的重复率打算，算一半6G吧，再来说你们的速度：
if (ht1.Contains(str3) //要在6G的空间进行object 类型检索
if (ht2.Contain(str3) //要在6G的空间进行第二次object 类型检索

比我的BOOL比较更快？我想2G次的检索下来，速度估计会慢N^N^N 倍吧？呵呵。。至于其它朋友的string 检索就不提了。另外，我要告诉你的是哈希表的优势不是你这么用的，它的原理来自堆栈映射检索（好似微软的emm386 管理），它要求有一个键和一个值，在检索时只要检索键（好比内存映射页面地址），而不必检索宠大的值（好比扩展内存），这样可以大大的加快数据的获取速度，只要给出快而短的键就可以找出对应的宏大的值。。可不是你这么用的。。你这么用还不如用sortlist3，出现你所说的负数、小数，这在我的交集算法中都有相应的方法，就是全局小数点右移算法，人所共知F点比整数要慢，大部分的数据处理中都是使用移小数的方法按照你个人角度来取验，这不是正确的方法，系分员要求的是理性的比较，我在做数据处理不少年了，包括原来我们自己做的数据库系统（那时是DOS时代），我们在这方面是经过了不少的验证得出的结论。。

另外，我要提醒你，特别是sumtec(Psydian) 你的：for (int i=0; i<s1.Length;i++)可是2G*2 次检索，呵呵

补充你的：你说用sortlist，不敢认同，hash在任何时候都会比sort快，这就是为什么编译器都是使用hash而不是sort加二分查找你知道SQL知道oracle 吗？我问你，它们的主键是干嘛用的？好看吗？就是用来排序的，为什么要排序呢？呵呵，它们都有自己的算法优化，比如主键ID是数字自增，当对ID进行检索时，它们只要对表映射地址进行换算，比如 where id=10000，那么它们只要找 1000 除映射页大小的那一页就可以了，而不必从头开始检索。。;-(哪位再来反驳？特别欢迎设计过数据库的朋友。。

你搞错了吧？我的方法跟最大的数字没有任何关系，而根字符串的元素个素有关系。如果说字符串有int.MaxValue个元素，那么这个字符串本身就不可能建立起来，就算建立起来了，无论我的方式还是你的方式都不可能成功。另外，看来你不知道hash是什么意思吧？hash本身有一个固定的容量，这个容量的大小跟你的要插入的元素的内容是什么是没有任何关系的，而是由用户指定的（或者由一个算法根据已经存在的元素的个数进行调整的）。所以说添加一个最大值的元素并不需要申请2G的空间。"2，你所说的不少东西都是很偏激的，比如int.MaxValue 出现的情况可能的话，那就说明将可能有2G个元素？就按你说的，做最坏的打算，str1、2、3 全是int.MaxValue 也就是 2G 个不同大小的元素，用你的方法试试："
—— 不对吧？有int.MaxValue出现的话就一定有2G个元素？如果你说我太偏激，那我举一个没有那么偏激的例子吧：
str1 = str2 = str3 = "1,5,10,50,100,500,1000,5000,10000,50000,100000,500000,1000000,5000000,10000000,5000000,100000000"
这里每个字符串有16个元素，但是你程序中的MaxOf为100000000吧？（错了请指教）对于这个例子，额外占用的空间是多少？400MB*3=1.2GB
我没算错吧？但是如果用hashtable，能够占用个10KB就了不起了。至于说为什么数据库不使用hash，那是因为hash不可能对赴超大规模的数据的。最好的情况下hash至少会占用4N*2=8N个字节的额外空间，而排序完成之后是占用的额外空间可能只有4N个字节，而且数据库使用的是外排序，原理跟内排序（再内存当中的）不是完全一样的，这里就不讨论了。此外还有两点制约着数据库使用hash：1、hash需要产生hashcode，而数据库面对的类型比较多，如果每个都要产生hashcode的话，编写数据库系统的工作量会比较大。当然，.NET Framework中每一个类型都能够产生哈希值，所以用hashtable比较方便。2、数据库本身需要排序相关的查询，而且查询的次数远远超过插入的次数，因此对于排序所带来的性能损失并不会非常在意，相反，这样每次进行排序相关的查询的时候就不需要再次排序了，而如果用hash表，插入的时候是不需要排序，但是每次进行排序相关的查询的时候都需要再次排序，显然性能损失更大！
问题是这个题目没有要求排序，就算是要求排序也只需要添加一次对结果的排序操作就可以了，而不需要每次插入都进行一次排序。（有什么不对的话请指教）一般说来元素的个数在10M个以内，我想用hash都会比sortlist快得多，因为hash增加一个元素只对一个元素进行计算，而sort增加一个元素就需要全体排序一次，很费时间的，就算是插入，运算量至少也会有O(Log2(N))。我上次忘了问你了，你的方法通用吗？如果是浮点数序列"1.2, 1.3, 3.3"你怎么应付？如果是负数序列"-1,-2, 3"你又怎么应付？如果要求改成抽象字符"A, 3, 我"你又打算怎么应付？如果你有什么问题，请您先用你的第二个方法试一下我上面所举的那个例子：
str1 = str2 = str3 = "1,5,10,50,100,500,1000,5000,10000,50000,100000,500000,1000000,5000000,10000000,5000000,100000000"这里的元素个数虽然少，但是你能够确保1000个元素的字符串当中不会包含100000000这个数字吗？（btw, 如果用hash的话额外占用的空间顶多100k）
如果成功了再说行吗？

To lostinetdotcom(思考=储存+选择+变异) :你的方法满有意思的，不过有一个很严重的bug，就是循环中发现没有这个元素的时候要remove之后，会跳过一个元素。比如说：str1 = "1, 2, 3, 4, 5, 6"
str2 = "0, 3, 4, 5, 6, 8"
str3 = ...那么当第一个str1里面的1在str2里面找不到的时候，就会remove掉，然后这个时候
al = {"2", "3", "4", "5", "6"}
在然后continue，这个时候i就直接变成1了，这个时候al[0]就不会再次比较，因此，呵呵，除错了吧？明明2不是交集里面的内容，但是还是添加到结果里面去了。解决的办法非常简单，有两个方法：
continue之前i--; 或者
for (i = al.Length - 1; i >= 0; i--)
其实你的办法也不错，至少表面算起来有一个最优情况，可以说比谁都快：如果str1和str2的交集为空，那么时间复杂度就等于O(N/3)。（N元素总数，就是str1、str2、str3的元素个数的总数。）不过这里面有两个比较大的问题：Remove和"," + ary[k] + ","
这两个操作都比较耗时，后面那个我就不多说了，你后面都会用stringbuilder来加速了，这里为什么不改进一下呢？前面那个Remove嘛，要移动后面所有的元素的，你觉得呢？实际上由于你用到了Remove和IndexOf，我估计实际上的平均的时间复杂度应该为：（粗略计算）
n^2/14 + n^3/66^ 表示幂，不是异或。似乎次数比较高啊。

嘿嘿，你的意思是 str1 = "1,100000000" 就这二个元素或者不多那何必用我的第二个方法第一个方法就最简单了，我的第二个方法已经说了就是在对付大数据集时的情况至于小数，我已经说过了，用全局小数点右移。。交集中出现负数？嘿嘿，一起告诉你吧，我们都知道int32 的负数在16进制都是正数，比如 int i =18 = 0xffffffee; 那么我们的做法是将int 的ffffffee 扩容到更大的比如c#中的int64 那么负也将变成正，这样在交集找并集的算法我们前几年就已经研究过了其它就不多说了，你试试：string[] ary=new string[3];
System.Random rnd = new Random();
int min=0, max = 1000000;
for (int i=0; i<max; i++) {
ary[0] += (rnd.Next(min,max)).ToString() + ",";
ary[1] += (rnd.Next(min,max)).ToString() + ",";
ary[2] += (rnd.Next(min,max)).ToString() + ",";
}
ary[0] = ary[0].Remove(ary[0].Length-1,1);
ary[1] = ary[1].Remove(ary[1].Length-1,1);
ary[2] = ary[2].Remove(ary[2].Length-1,1);MessageBox.Show("生成完成，开始计时");
DateTime dt = DateTime.Now;GetPoc(ary[0],ary[1],ary[2],max); //开始处理double len = (DateTime.Now - dt).TotalSeconds;
MessageBox.Show(len.ToString());用你的方法和我的跑跑就知道了。。你不会又告诉我一定要 str1 = "1," + int.maxvelue 吧？那就用我的第一个方法员。。哈哈

to : sumtec(Psydian)
其实那个问题我是注意到的。
但是处理上却犯了编程习惯的错误。随便打个continue上去就以为OK了。
其实那个continue一点意义都没有~~~~","+ary[k]+","所需的时间根本就是可以忽略的。","+al[i].ToString()+","这里，C#会自动优化为string.Concat(string str0,string str1,string str2)的。
所以性能比建立StringBuilder要好.我只是写写代码来表示基本思路而已。
如果要优化，那可以这样：using System;
using System.Collections;
using System.Text;namespace ConsoleApplication1
{
class Class1
{
[STAThread]
static void Main(string[] args)
{
string[] ary=new string[3];//N?
ary[0]="0,1,5,7,12,15,18,20";
ary[1]="0,1,5,8,13,15,19,20";
ary[2]="1,5,6,12,14,15,18,20";
//..to..arr[N-1]=... int arylen=ary.Length; int minindex=0;
int minlen=ary[0].Length;
for(int i=1;i<arylen;i++)
{
if(ary[i].Length<minlen)
{
minindex=i;
minlen=ary[i].Length;
}
} ArrayList al=new ArrayList(ary[minindex].Split(",".ToCharArray())); for(int k=0;k<ary.Length;k++)
{
if(k==minindex)
continue; string str=","+ary[k]+","; int alcount=al.Count;
int i=0;
while(i<alcount)
{
if(str.IndexOf(","+al[i].ToString()+",")==-1)
{
al.RemoveAt(i);
alcount--;
continue;
}
i++;
}
} StringBuilder sb=new StringBuilder();
foreach(string s in al)
{
if(sb.Length!=0)sb.Append(",");
sb.Append(s);
}
Console.WriteLine(sb);
}
}
}
我觉得这个程序，内存分配得是很小的。
它非常容易理解。算法不限于ary元素的个数，也不限制于数字的情况。当然，它还可以继续优化：
如果大多数情况是2，3个元素的。那么可以分开来进行处理。
如果参数的元素的排列顺序是一致的，那么可以在str.IndexOf上排除已经搜索过的位置。

哦。。还有。
不知道你有没有看过ArrayList.RemoveAt的算法没有。
我觉得它已经非常快了。当然，我觉得用双向链来储存那就更快了。

To ArLi2003(阿利正版 [上海有好工作叫我]) :
……
你自己看看自己的程序：
if (i<s1.Length) b1[int.Parse(s1[i])] =true;你写的是int.Parse，又不是uint.Parse，我说的问题就是存在的。而且就算你改成uint.Parse，你认为就没错了？uint.Parse("-1")会得到一个正数？似乎要改成 (uint) int.Parse才行。
嘿嘿，你的意思是 str1 = "1,100000000" 就这二个元素或者不多那何必用我的第二个方法第一个方法就最简单了，我的第二个方法已经说了就是在对付大数据集时的情况——怎么说你才明白呢？我的意思不是这样，而是比如有10000个元素，然后里面有一个是100000000，那么会怎么样呢？你是不是应该用第二个算法去解决呢？问题不就出来了吗？难道为了把这个问题表现出来，我非得给出一个10000个元素的例子出来吗？我用"1,100000000"这个例子就不行吗？好，不明白的话这么给你一个例子好了：string s;
for (i = 0; i<10000; i++)
    s = Random.Next(100000000, 200000000).ToString() + ",";
s = s.TrimEnd(",");GetPoc(s, s, s, 200000000);100000000 ～ 200000000   也至少有100000000个元素的空间，我没有说错吧？至于小数，我已经说过了，用全局小数点右移。
—— 啊！这么解决啊？那还要计算右移多少位？如果是3.33333333333333，那岂不是要变成333333333333333？那跟我提到的100000000问题不是一回事？
没错，bool是很快的，但是有时候要考虑会用多少空间。……  ……………  …………  ……………  ……  …………  ……………  …………  …………………

To lostinetdotcom(思考=储存+选择+变异):
呵呵！你的方法确实也不错，也许我错了，不过就算忽略了Remove，时间复杂度可能还是有O(n^2/14)左右。至于那个","+al[i].ToString()+"," ，我觉得也许你是对的，改成stringbuilder不会有改善，主要不是concat的效率高，而是stringbuilder对于不断地进行类似s+=t这一类的操作才会有改善。不过总觉得这个操作有点多余……我像是否可以这么改善：ary[0] = ary[0].Replace(",", ":,:");
ary[1] = ary[1].Replace(",", ":,:");
ary[2] = ary[2].Replace(",", ":,:");string str= "," + ary[k] + ",";
str = str.Replace(",", ":,:");那么后面就不用","+al[i].ToString()+","了。当然，还可以写得稍微好一点。不过我觉得似乎用hash比用IndexOf要快一点。

小弟有一个想法，
先把
ary[1]="0,1,5,8,13,15,19,20"; ==>"0,1,5,8,13,15,19,20,";
ary[2]="1,5,6,12,14,15,18,20"; ==>"1,5,6,12,14,15,18,20,";用一次for把ary[0]中的数字提出来进行比较
string[] strs=ary[0].Split(new Char[]{','});
foreach(string st in strs)
{
if((ary[1].Indexof(st + ",")>0) && (ary[2].Indexof(st + ",")>0))
Response.write(st+"<br>");
}

调试易

查找交集算法，有一点难度（欢迎大家讨论）

解决方案 »