CodingBat commonTwo方法，幫忙檢查一下輸出？

Question

問題摘要： 給定兩個字符串數組，返回一個整數，表示它們之間有多少匹配（忽略重複項）。

真正的答案：輸出 http://www.javaproblems.com/2013/11/java-ap-1-commontwo-codingbat-solution.html

我的代碼

public int commonTwo(String[] a, String[] b) { 
    int count = 0; 
    boolean done = false; 
    for (int i = 0; i<a.length-1; i++){ 
     if(a[i].equals(a[i+1])){ 
     i++; 
     for (String j:b) 
      if (a[i].equals(j) && !done){ 
      done = true; 
      count++; 
      } 
     } 
     else{ 
     for (String j:b) 
      if(a[i].equals(j) && !done){ 
      done = true; 
      count++; 
      } 
     } 
    done = false; 
    if(i == a.length-2) 
     for (String j:b) 
      if (a[i+1].equals(j) && !done){ 
      done = true; 
      count++; 
      } 
    } 
    return count; 
} 

圖片：[1]：http://i.stack.imgur.com/0esjC.png

那麼，它的目的是做的是通過所有的數組a，如果它等於下一個，則轉到該索引，然後在數組之間存在匹配時添加進行計數。完成的布爾值被用來使它成爲它，所以它不會添加以計算是否有與a相匹配的b的重複項，並且一旦找到匹配項就結束它。

最後，

if(i == a.length-2) 

是爲了使它所以如果這是最後的索引號前一秒（作爲最後一個索引號不會在某些情況下進行檢查），以及不一樣的最後一個索引號，然後在檢查最後一個索引號之後檢查最後一個索引號的匹配。我明白爲什麼會出現這兩種錯誤，並且想知道可以採取什麼措施來解決這個問題，特別是針對第二個/關於代碼的評論。另外，我注意到的第三個問題是（[「a」]，[「a」]）→1但代碼將導致0.

Answer 1

這個問題可以做到線性時間O（N）這是數組a和b的單遍歷。

你應該只要增加i爲相同的字符串appears.So

if(a[i].equals(a[i+1])) 
     i++; 

應

while(i+1<a.length&&a[i].equals(a[i+1])){ 
     i++;} 

也可換成你不需要去通過整個陣列b爲一個字符串數組a，因爲兩者都是按字母順序排列的。只應比較數組b中的字符串，只要沒有匹配。一旦找到匹配， d請記住索引和下一次匹配應該從該索引開始繼續，以便爲陣列b

此外，您不需要布爾變量done。

牢記這些事情正確的代碼是：

public static int commonTwo(String[] a, String[] b) { 
    int count = 0;   
    int j=0,i;  
    for (i = 0; i<a.length-1&&j<b.length-1;){ 
     //SKIP DUPLICATES FOR ARRAY a 
     while(i+1<a.length&&a[i].equals(a[i+1])){ 
     i++;} 
     //SKIP DUPLICATES FOR ARRAY b 
     while(j+1<b.length&&b[j].equals(b[j+1])){ 
     j++;} 

     //MATCH THE STRINGS FROM ARRAY a AND ARRAY b 
     while(i<a.length&&j<b.length&&a[i].compareTo(b[j])!=0) 
     { 
     //INCREMENT I IF STRING IN ARRAY a IS LESS THAN STRING IN ARRAY b 
     if(a[i].compareTo(b[j])<0) 
     ++i; 
     //INCREMENT J IF STRING IN ARRAY b IS LESS THAN STRING IN ARRAY a 
     else ++j; 
     } 

     //IF ABOVE LOOP BREAKS BECAUSE OF MATCH 
     if(i<a.length&&j<b.length) 
     {count++; ++j; ++i;} 
    } 

    //IF THE LAST ELEMENT OF ARRAY a IS LEFT FOR COMPARISON 
    if(i==a.length-1) 
    { 
    while(j<b.length) 
    { 

     //SKIP DUPLICATES OF ARRAY b 
     while(j+1<b.length&&b[j].equals(b[j+1])) 
     ++j; 

     if(a[i].equals(b[j])) 
     {++count;} 
     ++j; 
    } 
    } 
    //IF THE LAST ELEMENT OF ARRAY b IS LEFT FOR COMPARISON 
    if(j==b.length-1) 
    { 
    while(i<a.length) 
    { 
     //SKIP DUPLICATES OF ARRAY a 
     while(i+1<a.length&&a[i].equals(a[i+1])) 
     ++j; 

     if(a[i].equals(b[j])) 
     ++count; 
     ++i; 
    } 
    } 
    return count; 
    }