截止到目前我已經寫了 600多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666
題中說了每艘船最多可同時載兩人，要讓船最少，就應該讓載兩人的船最多，解題思路就是先對陣列進行排序，我們優先考慮體重最大的，
- 如果體重最大的和體重最小的可以同時乘坐一艘船，就讓他倆乘坐一條船，
- 如果體重最大的和體重最小的不能同時乘坐一艘船，那么體重最大的和其他任何人都不可能同時乘坐一條船，我們只能給體重最大的單獨分配一條船，
原理比較簡單，我們來看下代碼，
public int numRescueBoats(int[] people, int limit) {
//先對陣列進行排序（人發重量按照從小到大的順序排序）
Arrays.sort(people);
//統計船的個數
int count = 0;
//從小到大排序，左邊的是最小的，右邊的是最大的
int left = 0;
int right = people.length - 1;
while (left <= right) {
//如果體重最大的和體重最小的可以單獨乘坐
//一條船，就讓他們同乘一條船
if (people[right] + people[left] <= limit)
left++;
//體重最大的每次都要減1
right--;
//使用船的數量
count++;
}
return count;
}
時間復雜度：O（nlog(n)），這個是排序使用的復雜度，
空間復雜度：O（log(n)），排序使用的空間復雜度，這個需要看Arrays.sort的原始碼，他呼叫的是DualPivotQuicksort類中的方法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/356150.html
標籤：其他
上一篇：利用算符優先級實作運算式的求值