题

1464. 数组中两元素的最大乘积

给你一个整数数组 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

析

题意是找出数组中最大的两个数i, j，然后返回(i-1)*(j-1)，可以直接使用两个变量遍历保存最大的两个数，并返回结果。同时也可以使用快速选择算法，找出最大的两个变量。两者的平均时间复杂度都是O(n)

解

一次遍历

func maxProduct(nums []int) int {
    var a, b int
    for _, v := range nums {
        if v >= a {
            a, b = v, a
        } else if v > b {
            b = v
        }
    }
    return (a-1) * (b-1)
}

快速选择

func quickSelect(nums []int, left, right int, k int) {
    if left >= right {
        return
    }

    l, r := left, right
    // 交换的逻辑和快速选择一样
    p := l
    for l < r {
        for l < r && nums[r] < nums[p] {
            r--
        }
        for l < r && nums[l] >= nums[p] {
            l++
        }
        if l >= r {
            break
        }
        nums[l], nums[r] = nums[r], nums[l]
    }
    nums[l], nums[p] = nums[p], nums[l]

    if l == k {
        // 分好了，停止
        return 
    } else if l > k {
        // 左侧l个数据个数大于k，需要缩减数量
        quickSelect(nums, left, l - 1, k)
    } else {
        // 左侧l个数据个数小于K，需要增加数量
        quickSelect(nums, l + 1, right, k)
    }
}

func maxProduct(nums []int) int {
    quickSelect(nums, 0, len(nums)-1, 2)
    return (nums[0] - 1) * (nums[1] - 1)
}

最后修改于 2022-08-26