leetcode-1464. 数组中两元素的最大乘积刷题笔记（c++）

ゞ 浴缸里的玫瑰 2023-02-22 13:40 129阅读 0赞

写在前面

  • 难度：简单

  • 排序、取第1/2个元素减1乘积

    • sort<nums.begin(), nums.end(), greater<int>()>

题目详情

  1. 给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
  3. 请你计算并返回该式的最大值。
  5. 示例 1：
  6.     输入：nums = [3,4,5,2]
  7.     输出：12 
  8.     解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。 
  10. 示例 2：
  11.     输入：nums = [1,5,4,5]
  12.     输出：16
  13.     解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。
  14. 示例 3：
  15.     输入：nums = [3,7]
  16.     输出：12
  18. 提示：
  20. 2 <= nums.length <= 500
  21. 1 <= nums[i] <= 10^3

ac代码

  • 方法1：排序 + 求积

    class Solution
    {

    public:

    1. int maxProduct(vector<int>& nums)
    2. {
    4.     sort(nums.begin(), nums.end(), greater<int>());
    5.     return (nums[0]-1)*(nums[1]-1);
    6. }

    };

  • 方法2：单层循环 + 多个临时变量（第1/2最大值）

    class Solution
    {

    public:

    1. int maxProduct(vector<int>& nums)
    2. {
    4.     int max1 = 0, max2 = 0;
    5.     for(int i=0; i<nums.size(); i++)
    6.     {
    8.         if(nums[i]>=max1)
    9.         {
    11.             max2 = max1;
    12.             max1 = nums[i];
    13.         }
    14.         // 首部最大值，第2最大值无法更新
    15.         else if(nums[i]<=max1 && nums[i]>max2)
    16.             max2 = nums[i];
    17.     }
    18.     return (max1-1)*(max2-1);
    19. }

    };

  • 测试代码

    include

    include

    using namespace std;

    int maxProduct(vector& nums)
    {

    1. int max1 = 0, max2 = 0;
    2. for(int i=0; i<nums.size(); i++)
    3. {
    5.     if(nums[i]>=max1)
    6.     {
    8.         max2 = max1;
    9.         max1 = nums[i];
    10.     }
    11.     else if(nums[i]<=max1 && nums[i]>max2)
    12.         max2 = nums[i];
    13. }
    14. return (max1-1)*(max2-1);

    }

    int main()
    {

    // vector vv = {10,2,5,2};
    // vector vv = {3,4,5,2};
    //vector vv = {1,5,4,5};

    1. vector<int> vv = {
    2. 3, 7};
    4. cout << maxProduct(vv) << endl;

    }

  • 参考文章

    • leetcode（1464） 数组中两元素的最大乘积

发表评论

表情：
评论列表 （有 0 条评论，129人围观）

还没有评论，来说两句吧...

相关阅读