Giảm thiểu Tổng cặp tối đa trong mảng Giải pháp LeetCode cho biết tổng cặp của một cặp [a,b] bằng a+b. Tổng cặp tối đa là tổng cặp lớn nhất trong danh sách các cặp
- Ví dụ: nếu chúng ta có các cặp [2,6], [1,3] và [5,4], tổng các cặp tối đa sẽ là max[2+6, 1+3, 5+4] = max[8 . 9] = 9
Cho mảng nums có độ dài n chẵn, ghép các phần tử của nums thành n / 2 cặp sao cho
- Mỗi phần tử của nums nằm trong chính xác một cặp và
- Tổng số cặp tối đa được giảm thiểu
Trả về tổng cặp tối đa được tối thiểu hóa sau khi ghép nối các phần tử một cách tối ưu
Ví dụ
Trường hợp thử nghiệm 1
Đầu vào
số = [3,5,2,4,6,8]
đầu ra
10
Trường hợp thử nghiệm 2
Đầu vào
số = [1,5,3,4,6,7]
đầu ra
9
Giải trình
i] Đối với trường hợp thử nghiệm đầu tiên, chúng ta có thể có các cặp như [2,8], [3,6] và [4,5]. Tổng của các cặp này là 10, 9 và 9. Tổng tối đa là 10
ii] Đối với trường hợp kiểm tra thứ hai, chúng ta có thể có các cặp như [1,7], [3,6] và [4,5]. Tổng của các cặp này là 8, 9 và 9. Tổng tối đa là 9
Tiếp cận
Ý tưởng
Ở đây chúng ta cần giảm thiểu tổng cặp tối đa. Vì vậy, ý tưởng cơ bản là chúng ta có thể ghép các số như [lớn thứ nhất và nhỏ thứ nhất], [lớn thứ 2 và nhỏ thứ 2], v.v. Bằng cách này chúng ta có thể giảm thiểu tổng. Chúng tôi có thể cảm thấy rằng nếu chúng tôi ghép nối [lớn thứ 2 và nhỏ thứ 1], nó sẽ giảm thiểu tổng. Nhưng theo cách này, chúng ta sẽ phải ghép [số lớn thứ nhất] với một số khác sẽ lớn hơn số nhỏ thứ nhất, điều này sẽ làm tăng tổng tối đa. Chúng ta có thể 2 con trỏ, con trỏ trái và con trỏ phải. Mỗi lần chúng ta sẽ tăng con trỏ bên trái và giảm con trỏ bên phải và kiểm tra giá trị lớn nhất
Mã số
Chương trình Java để giảm thiểu tổng số cặp tối đa trong giải pháp LeetCode của mảng
class Solution {
public int minPairSum[int[] nums] {
Arrays.sort[nums];
int left = 0, right = nums.length-1;
int maxSum = 0;
while[left[nums[left++]+nums[right--]]?maxSum:[nums[left-1]+nums[right+1]];
}
return maxSum;
}
}Chương trình C++ để giảm thiểu tổng số cặp tối đa trong mảng Giải pháp LeetCode
class Solution {
public:
int minPairSum[vector& nums] {
sort[begin[nums], end[nums]];
int left = 0, right = nums.size[]-1;
int maxSum = 0;
while[left[nums[left++]+nums[right--]]?maxSum:[nums[left-1]+nums[right+1]];
}
return maxSum;
}
};Phân tích độ phức tạp để giảm thiểu tổng số cặp tối đa trong giải pháp LeetCode mảng
Thời gian phức tạp
Ở đây chúng tôi đang lặp lại mảng bằng kỹ thuật hai con trỏ. Vì vậy, sẽ mất O[n/2] ≡ O[n] thời gian. Nhưng trước đó, chúng ta đang sắp xếp mảng. Phải mất O[nlogn] thời gian. Nó chi phối sự phức tạp về thời gian. Vì vậy, độ phức tạp thời gian tổng thể sẽ là O[nlogn]
Cho một mảng arr[], đếm số cặp arr[i], arr[j] sao cho arr[i] + arr[j] là lớn nhất và i < j
Example :
Input : arr[] = {1, 1, 1, 2, 2, 2}
Output : 3
Explanation: The maximum possible pair
sum where i