Home 成长之路 Leetcode题解 数组之排序

数组之排序

给你一个整数数组 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 。
解题思路:关键在于找出第一大和第二大的值;
方法一:冒泡排序,求(nums[0])*(nums[1])的值;
方法二:双指针,一个指向最大,一个指向第二大,不用排序;
int maxProduct(int* nums, int numsSize){
int first = nums[0] > nums[1] ? nums[0] : nums[1];
int second = nums[0] > nums[1] ? nums[1] : nums[0];
for (int i = 2; i < numsSize; i++) {
if (nums[i] >= first) {
second = first;
first = nums[i];
} else {
if (nums[i] > second) {
second = nums[i];
}
}
}
return (first – 1) * (second – 1);
}

SIMILAR ARTICLES

0 120

0 112

发表评论

发表评论