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 中的至少一個,沒有機會從剩余的數字中形成兩對。

TA貢獻1876條經驗 獲得超6個贊
你可以這樣解決它:
一世。排序數組。
ii. 對于每個數字a找到包含 >= 2*b 的數組的最左邊位置p 。然后你可以數出有多少滿意。
復雜度:O(nlogn)+nlogn
添加回答
舉報