亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

將數組中的數字 (a,b) 配對,使得 a*2 >=b

將數組中的數字 (a,b) 配對,使得 a*2 >=b

開心每一天1111 2022-05-20 18:42:51
我正在嘗試以這樣的方式解決數組中的配對數字(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。數組長度的一半(如果長度為奇數,則向下舍入)。您可以以任何您喜歡的方式配對數字。對于非負ab如果a * 2 < b,只需交換ab,您將得到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 中的至少一個,沒有機會從剩余的數字中形成兩對。


查看完整回答
反對 回復 2022-05-20
?
HUX布斯

TA貢獻1876條經驗 獲得超6個贊

你可以這樣解決它:

一世。排序數組。

ii. 對于每個數字a找到包含 >= 2*b 的數組的最左邊位置p 。然后你可以數出有多少滿意。

復雜度:O(nlogn)+nlogn



查看完整回答
反對 回復 2022-05-20
  • 2 回答
  • 0 關注
  • 130 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號