題目描述
給你一個整數陣列 nums，請你選擇陣列的兩個不同下標 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值，
請你計算并回傳該式的最大值，
示例 1：
輸入：nums = [3,4,5,2]
輸出：12
解釋：如果選擇下標 i=1 和 j=2（下標從 0 開始），則可以獲得最大值，(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 ，
示例 2：
輸入：nums = [1,5,4,5]
輸出：16
解釋：選擇下標 i=1 和 j=3（下標從 0 開始），則可以獲得最大值 (5-1)*(5-1) = 16 ，
示例 3：
輸入：nums = [3,7]
輸出：12
提示：
2 <= nums.length <= 500
1 <= nums[i] <= 10^3
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/maximum-product-of-two-elements-in-an-array
題目分析
從描述中可以得出以下幾個解題關鍵資訊：
- 同一個陣列，但下標不同的兩個數
- 從所有結果中取最大值，即nums[i]和nums[j]是陣列中最大的兩個數
解題思路
暴力解法
能否簡單的使用雙重回圈暴力破解呢？不能，因為暴力破解會存在下標i=j的情況，假設nums[i]是陣列中最大的值，那么就nums[i]=nums[j]，這兩個數相乘就成了最大的結果了，所以不能簡單的使用雙重回圈，
優化后的暴力解法
題目的關鍵資訊是i和j不同，那么在雙重回圈中去除掉i=j的情況不就行了？
舉個栗子，i和j回圈的所有值是i=1,2,3....；j=1,2,3....；進行雙重回圈的時候i=1,j從1開始到nums.length-1，將i=j的情況去掉就是在初始化時讓j=i+1，同理當i=2時，j也不能小于2，因為當i=1的時候已經計算了[1,2]的結果，所以為了降低時間復雜度，不能再計算[2,1]的結果了，所以j>i即j=i+1，代碼如下：
public int maxProduct(int[] nums) {
//時間復雜度O(n^2) 時間換空間
int max = 0;
for(int i=0;i<nums.length;i++) {
for(int j = i+1;j<nums.length;j++) {
max = Math.max((nums[i]-1)*(nums[j]-1), max);
}
}
return max;
}
排序解法
既然是要取陣列中兩個不同的最大值，那么直接先進行排序然后取最前或者最后兩個數不就行了？采用快速排序，平均時間復雜度為O(nlog2n)，代碼就不列出了，網上很多實作，
空間換時間解法
能不能只進行一次遍歷就解決呢？可以，
既然要保證取到最大的兩個數，那么是不是可以給兩個變數n1、n2，每次從nums陣列中取一個數值替換n1、n2中更小的那個呢？這樣nums陣列只需要一次遍歷，n1、n2也一直保證是當前遍歷到的nums陣列中最大的兩個數，代碼如下：
public int maxProduct(int[] nums) {
//時間復雜度O(n),每次都將兩個數里面最小的替換掉 空間換時間
int n1=0,n2=0;
for(int i=0;i<nums.length;i++) {
if(n1<=n2) {
n1=Math.max(nums[i], n1);
} else {
n2=Math.max(nums[i], n2);
}
}
return (n1-1)*(n2-1);
}
總結
思維擴展
從這一道題想到了另外一題，如：給定一個陣列，從中隨機取3個數，共有多少種取法，
就是一個排列組合的問題，其實也是要去除重復的組合，可以采用暴力解法的優化方式去解，只是回圈變成了三重，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502727.html
標籤：其他
上一篇：向量距離與相似度函式