Easy

题目描述

给你一个长度为 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

解题思路

这道题要求我们找出数组中有多少个主导索引。对于每个索引 i，我们需要检查 nums[i] 是否大于其右侧所有元素的平均值。

解题思路

方法一：直接模拟（推荐） 由于数组长度最多为 100，我们可以采用暴力模拟的方法：

  1. 遍历数组中除最后一个元素外的每个位置 i
  2. 对于每个位置 i，计算从 i+1 到数组末尾所有元素的平均值
  3. 比较 nums[i] 与该平均值的大小关系
  4. 如果 nums[i] 大于平均值，则该索引是主导索引

方法二：后缀和优化 为了避免重复计算，我们可以使用后缀和：

  1. 预计算从每个位置到数组末尾的元素和
  2. 对于每个位置 i，直接用预计算的和除以元素个数得到平均值

由于题目数据规模较小，两种方法的性能差异不大，但第一种方法更简洁易懂。

需要注意的边界条件：

  • 数组最后一个元素不能是主导元素
  • 当数组长度为 1 时，没有主导元素
  • 比较时要注意浮点数精度问题

代码实现

class Solution {
public:
    int dominantIndices(vector<int>& nums) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n - 1; i++) {
            int sum = 0;
            for (int j = i + 1; j < n; j++) {
                sum += nums[j];
            }
            double average = (double)sum / (n - i - 1);
            if (nums[i] > average) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def dominantIndices(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        
        for i in range(n - 1):
            right_sum = sum(nums[i + 1:])
            average = right_sum / (n - i - 1)
            if nums[i] > average:
                count += 1
        
        return count

public class Solution {
    public int DominantIndices(int[] nums) {
        int n = nums.Length;
        int count = 0;
        
        for (int i = 0; i < n - 1; i++) {
            int sum = 0;
            for (int j = i + 1; j < n; j++) {
                sum += nums[j];
            }
            double average = (double)sum / (n - i - 1);
            if (nums[i] > average) {
                count++;
            }
        }
        
        return count;
    }
}

var dominantIndices = function(nums) {
    const n = nums.length;
    let count = 0;
    
    for (let i = 0; i < n - 1; i++) {
        let sum = 0;
        for (let j = i + 1; j < n; j++) {
            sum += nums[j];
        }
        const average = sum / (n - i - 1);
        if (nums[i] > average) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n²)
空间复杂度O(1)

说明：

  • 时间复杂度：外层循环遍历 n-1 个元素，内层循环平均遍历 n/2 个元素，总体为 O(n²)
  • 空间复杂度：只使用了常数个额外变量，为 O(1)