跳转至

3833. 统计主导元素下标数

题目描述

给你一个长度为 n 的整数数组 nums。

当下标 i 满足以下条件时，该下标处的元素被称为 主导元素：nums[i] > average(nums[i + 1], nums[i + 2], ..., nums[n - 1])

你的任务是统计数组中 主导元素 的下标数。

平均值 是指一组数的总和除以该组数的个数得到的值。

注意：数组的 最右边元素 不算作 主导元素 。

 

示例 1：

输入： nums = [5,4,3]

输出： 2

解释：

  • 在下标 i = 0 处，值 5 是主导元素，因为 5 > average(4, 3) = 3.5。
  • 在下标 i = 1 处，值 4 是主导元素，相对于子数组 [3]。
  • 下标 i = 2 不是主导元素，因为它右侧没有元素。因此答案是 2。

示例 2：

输入： nums = [4,1,2]

输出： 1

解释：

  • 在下标 i = 0 处，值 4 是主导元素，相对于子数组 [1, 2]。
  • 在下标 i = 1 处，值 1 不是主导元素。
  • 下标 i = 2 不是主导元素，因为它右侧没有元素。因此答案是 1。

 

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100​​​​​​​

解法

方法一：逆序遍历

我们可以从后向前遍历数组，维护一个后缀和 \(\text{suf}\)，表示当前元素右侧所有元素的和。对于每个元素，判断其是否大于右侧元素的平均值 \(\frac{\text{suf}}{n - i - 1}\)，如果是，则将答案加一。最后返回答案即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\text{nums}\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def dominantIndices(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        suf = nums[-1]
        for i in range(n - 2, -1, -1):
            if nums[i] > suf / (n - i - 1):
                ans += 1
            suf += nums[i]
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int dominantIndices(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int suf = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] * (n - i - 1) > suf) {
                ans++;
            }
            suf += nums[i];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int dominantIndices(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        int suf = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] * (n - i - 1) > suf) {
                ans++;
            }
            suf += nums[i];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func dominantIndices(nums []int) int {
    n := len(nums)
    ans := 0
    suf := nums[n-1]
    for i := n - 2; i >= 0; i-- {
        if nums[i]*(n-i-1) > suf {
            ans++
        }
        suf += nums[i]
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function dominantIndices(nums: number[]): number {
    const n = nums.length;
    let ans = 0;
    let suf = nums[n - 1];
    for (let i = n - 2; i >= 0; --i) {
        if (nums[i] * (n - i - 1) > suf) {
            ans++;
        }
        suf += nums[i];
    }
    return ans;
}

评论