谁能用最高效率的方法算出这道题

Question

int[] x=new int[100];
int[] y=new int[100];
谁能用最高效率的方法求出x和y中相同的元素并赋给数组c;
不要说用双循环,那效率不是最高的

Answer 1

int k = 0;
for(int i = 0 ; i < 100 ; i++){
if (x[i] = y [i]){
c[k] = x[i];
k++;
}
}

Answer 2

java_augur的方法不行吧，而且比较应该是两个=号要是定义的数组有规律就容易了，要是没有规律又不用两次循环，学习中......

Answer 3

用hash表了，把两数组的值作为关键字，经过mapping成数组C的下标，再和数组C中的值做比较，如果值为无效则赋值，相等则忽略，不等则下标加1。
给出伪代码，暂不考虑数据容错：
const int ARRAY_LEN = 100; //A,B 数组长度，C为A+B长度的和
int mapping( const int& data[], const int i ) //映射公式
{
  int index = data[i] % ( ARRAY_LEN * 2 ); 
  for ( int t = 0; t < ARRAY_LEN * 2; ++t ){
    if ( C[index] == EMPTY || C[index] == data[i]){
      return index;
    } else if ( C[index] != data[i] ){  
      index = ( index + 1 ) % ARRAY_LEN;
    }  
  } }int main()
{
  int index;
  for ( int i = 0; i < ARRAY_LEN; ++i ) {
    index = mapping( A, i );
    C[index] = A[i];
    index = mapping( B, i );
    C[index] = B[i];
  }
  //...  
}从数学的概念来说，也就是A和B两集合，取他们的交集C。实现方法有很多种。

Answer 4

index = ( index + 1 ) % ARRAY_LEN;
改为
 index = ( index + 1 ) % ( ARRAY_LEN * 2); //也就是取C数组的下标，但是不能越界的意思

Answer 5

int[] x = new int[100];
int[] y = new int[100];
int[] c;
Map aMap = new HashMap();
List aList = new ArrayList();

for(int i = 0 ; i < 100 ; i++){
  aMap.put(String.valueOf(x[i]),String.valueOf(x[i]));
}

for(int i = 0 ; i < 100 ; i++){
  Object obj =  aMap.get(String.valueOf(y[i]));
  if (obj  != null) {
    aList.add(String.valueOf(y[i]));
  }
}

c = new int[aList.size()];

for (int i = 0; i < aList.size(); i++) {
  c[i] = ((Integer)aList.get(i)).intValue();
}

Answer 6

//不用双循环是吧,也一个样"行";int i=0,j=0,k=0;
while(j<100){
    if(a[i]==b[j]){
        c[k++]=a[i];
    }else{
        if(i<100){i++;continue;}
    }j++;
}

Answer 7

1,mad2000s(MAD) ( )看起来是单循环,可是还是双循环的效果,而且更难看懂,嘿嘿...
2,对于Hash的说法,到底能不能提高效率?100*100对于CPU来说不到一个时钟周期已经算完,走Hash的话,存储的时候要先String化,再根据hashCode存储到对应的Table中,读取Hash时,也要先String化,再根据HashCode找到对应的桶,还要经过若干次的遍历找到值,真的提高了效率吗?

Answer 8

我不知道JAVA的Hash数据结构是怎么实现的，但是存储时候先要转String是没有必要的。这个问题的Hash的映射函数是自定义代码，需要自己写。fatsky()的代码虽然也使用的HASH，但是Object obj =  aMap.get(String.valueOf(y[i]));这句包含了一重的循环。使用Hash的效率是O(N)的，使用两个循环的效率是O(N^2)，O运算符是指“渐进状态”下的算法效率。性能高的算法以牺牲可读可理解性为代价，对于规模有限的问题代码越简单越好，讨论复杂的高性能算法没太大意义。

Answer 9

liu_you(滴水藏海) 我说老兄,如何才能不要两个循环是不可能的.
ZhangYv(暴雪公司首席水管工)的哈希算法也是两个循环呀.