java編號對算法

-2

我最近一直在看一個YouTube視頻拍攝的問題，我看了一個軟件開發人員在Google上的位置。在視頻中，候選人被給予了一個隨機數字陣列，並詢問他們將如何開發一個程序來計算數組中的總數對，總數爲8.因此，例如，給定數組{1,3， 4,5,7}，答案將是2，（1,7）和（3,5）。在繼續觀察候選人如何解決這個問題之前，我決定自己去一趟。正如你從我用Java寫的這個問題的粗略方法中看到的那樣，我決定使用一個嵌套for循環遍歷每個數字組合，並相應地使用if語句進行評估。我相信你會同意，這個代碼在很多方面都很貼切：java編號對算法

（a）爲了避免像（1,7）和（7,1）這樣的遞歸對，我限制了迭代外循環爲nums.length/2。這實際上適用於有限數量的集合，但是當呈現諸如（0,0,0,0,0,1,3,4,5,7）這樣的數字集合時當然會失敗。（b）爲了避免在嵌套的for循環中將數字4作爲一對，我添加了條件代碼nums [i]！= nums [j]。同樣，如果帶有包含合法對（4,4）的數字集（如{1,3,4,4,5,7}），則需要將其添加到計數中。

作爲一個編程的相對新手，好吧......我能說什麼？......我給了我最好的照片。但我非常希望從更多經驗的程序員身上學習，並且非常樂於聽到關於如何解決這類問題的其他想法。對此的任何想法......最感激。

package numberpairs; 

import java.util.Arrays; 

public class DisApp { 

public static void main(String[] args) { 

    int[] nums = {4,2,6,1,5,7,3}; 

    Arrays.sort(nums); 
    System.out.println(Arrays.toString(nums)); 

    int count =0; 
    for(int i=0; i<nums.length/2; i++){ 
     for(int j=0; j<nums.length; j++){  
      if(nums[i]+nums[j]==8 && nums[i] != nums[j]){ 
       count++;        
      }  
     }    
    } 
    System.out.println(count); 
    } 
}

來源

2017-07-31 Mike

代碼審查問題應發佈在代碼審查Stackexchange上。不在這裏。 –

你似乎沒有錯誤。 Code Review Stack Exchange將是此 –

的正確站點如果你允許我，你應該能夠自己解決你的錯誤，因爲你自己確定了它們。 – Nathan

的簡單的想法：爲每輸入一個數i我們應該找到數等於8-i那名前面輸入的數量。這可以用一個HashMap來實現：

int S = 8; 
int[] input = {1,3,4,5,7,7,4}; 
Map<Integer, Integer> m = new HashMap<>(); 

int answer = 0; 
for (int i : input) { 
    int j = S - i; 
    if (m.containsKey(j)) { 
     answer += m.get(j); 
    } 

    if (m.containsKey(i)) { 
     m.put(i, m.get(i) + 1); 
    } else { 
     m.put(i, 1); 
    } 
} 
System.out.println(answer);

可運行版本：http://ideone.com/lqmuyL

這實現了O(n)平均情況時間複雜度爲online algorithm。

來源

2017-07-31 14:53:17 DAle

謝謝DAle，我會看看這個。 – Mike

java編號對算法

回答

相關問題