我正在嘗試以這樣的方式解決數組中的配對數字（a，b）a*2 >=b。其中 a 和 b 是輸入數組中的數字。例子：輸入：a[] = {1,2,3,4,5}輸出：2解釋：我們可以將 1 與 3 配對2 與 4 或 5輸入：a[] = {4,3,2,1,5}輸出：2解釋：我們可以將 1 與 3 配對2 與 4 或 5輸入：a[] = {4,3,2,1,5,6}輸出：3解釋：我們可以將 5 與 1 配對2 與 43 與 6我嘗試使用如下遞歸來解決問題，但這并沒有給出任何正確的結果。任何幫助，將不勝感激。對輸入數組進行排序如果a[start] * 2 >= [end] found then add 1to result recur for start +1andend - 1else為(start + 1, end),(start, end - 1)和 (start + 1, end - 1)a[start]想法與數組中的剩余元素匹配并獲得最大結果。 public static int countPairs(int[] a){ Arrays.sort(a); return countPairs(a,a.length,0,a.length-1); } public static int countPairs(int[] a, int n, int start, int end){ if(end == start){ return 0; } if(start >= n || end < 0){ return 0; } System.out.print("matching start: "+start + " and end "+end+" ");System.out.println("matching "+a[start] + " and "+a[end]); if(a[start] < a[end] && a[start] * 2 >= a[end] ){ int res = countPairs(a,n,start+1,end-1) +1; //System.out.print("inside if matching start: "+start + " and end "+end+" ");System.out.println("matching "+a[start] + " and "+a[end] + " count is "+res); return res; } else{ return max(countPairs(a,n,start+1,end) , countPairs(a,n,start,end - 1),countPairs(a,n,start+1,end - 1)); } }
2 回答
千巷貓影
TA貢獻1829條經驗 獲得超7個贊
我建議答案是a.length / 2。數組長度的一半（如果長度為奇數，則向下舍入）。您可以以任何您喜歡的方式配對數字。對于非負a和b如果a * 2 < b，只需交換a和b，您將得到a * 2 >= b。因此，由于配對需要兩個數字，因此您始終可以精確地形成與數組長度的一半一樣多的配對。
示例（來自評論）：[1, 2, 2, 2]。長度是4，長度的一半是2，所以應該有2對。讓我們檢查一下：(1, 2) 是一個不錯的對，因為 1 * 2 >= 2。(2, 2) 是另一個不錯的對，因為 2 * 2 >= 2。在這種情況下，我們甚至不需要任何交換 (on另一方面，相同的對也可以用于交換：2 * 2 >= 1 和 2 * 2 >= 2)。
如果數組可能包含負數，它并不總是有效。因此，您可能想要添加一個數組驗證來檢查它是否沒有。
您的解決方案出了什么問題？
您的遞歸算法是錯誤的。假設數組是 [2, 3, 7, 9]。顯然 (2, 3) 和 (7, 9) 是很好的對，所以這里有兩對。你描述你的算法的方式，因為 (2, 9) 不是一個有效的對，你丟棄 2 和 9 中的至少一個，沒有機會從剩余的數字中形成兩對。
HUX布斯
TA貢獻1876條經驗 獲得超6個贊
你可以這樣解決它：
一世。排序數組。
ii. 對于每個數字a找到包含 >= 2*b 的數組的最左邊位置p 。然后你可以數出有多少滿意。
復雜度：O(nlogn)+nlogn
添加回答
舉報
0/150
提交
取消