题目

给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。

请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

示例：

输入：nums = [1]

输出：0

解释：因为不存在其他数字，所以认为现有数字 1 至少是其他数字的两倍。

来源：力扣（LeetCode）

解答

解法1. 直接模拟法

通过两个变量，分别保存最大值下标和次大值下标，遍历完毕后根据条件进行返回。

class Solution {
public:
    int dominantIndex(vector<int> &nums) {
        int maxIndex = 0; // 最大值下标
        int lastIndex = -1; // 次大值下标

        int n = nums.size();
        if (n == 1) {
            return 0; // 只有一个元素，直接返回 0
        }

        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[maxIndex]) {
                lastIndex = maxIndex;
                maxIndex = i;
            } else if (lastIndex == -1 || nums[i] > nums[lastIndex]) {
                lastIndex = i;
            }
        }

        if (nums[maxIndex] >= (2 * nums[lastIndex])) {
            return maxIndex;
        } else {
            return -1;
        }
    }
};

解法2. 数组排序

通过pair分别存储原数组的下标和值，并进行排序，然后对最后一个和倒数第二个数进行二倍比较，然后决定是否返回下标。

class Solution {
public:
    int dominantIndex(vector<int> &nums) {
        int n = nums.size();

        vector<pair<int, int>> numss(n, {0, 0});

        for (int i = 0; i < n; ++i) {
            numss[i].first = nums[i];
            numss[i].second = i;
        }

        sort(numss.begin(), numss.end());

        if (numss[n-1].first >= (numss[n-2].first * 2)) {
            return numss[n-1].second;
        } else {
            return -1;
        }
    }
};