- 一、题目
- 二、解题
- （1）简单模拟题，O(n)，提交用时 4 ms，内存消耗 10.6 MB
- （2）第一种方法的优化（指代码长短上），时间复杂度依旧 O(n)，空间复杂度 O(1)
- （3）傻瓜遍历式（仅思路）
- （4）排序方法（仅思路）
略，请到 leetcode 查看题库的第 747 题至少是其他数字两倍的最大数。
二、解题 （1）简单模拟题，O(n)，提交用时 4 ms，内存消耗 10.6 MB先抓题目关键词：
①整型数组
②最大值唯一
③最大值是其余数的两倍以上
④满足返回最大值下标，否则返回 -1
题目要求判断最大值与其余数关系，所以我们首先就要找到最大值。
并且只要最大数是次大数的两倍以上，就一定满足最大数是其余数字的两倍以上，这很容易理解。
题目又要求返回值是下标，所以我们选择创建存储下标的变量，然后通过下标变量再来判断下标对应的数的大小，而不选择直接定义存储数大小的变量，这样最后就减少了转换的步骤。
代码及几个细节：
class Solution {
public:
int dominantIndex(vector& nums)
{
//数组长度
int len = nums.size();
//只有一个元素的情况
if(len == 1) return 0;
//找到最大数和次大数
//最大数和次大数下标
int max = 0,premax = 1;
//遍历计数器
int i = 1;
//记录最大数下标
while(i < len)
if(nums[max] < nums[i])
{
premax = max;
max = i++;
}
else if(nums[i] > nums[premax]) premax = i;
else ++i;
//最大数是次大数的两倍，返回最大数下标
if(2 * nums[premax] <= nums[max]) return max;
//否则返回 -1
else return -1;
}
};
几个细节：
1、特别要注意 0 的情况：
①最大数是 1，次大数是 0，这个情况是符合条件的
如果没有考虑这种情况，可能会有人最后一个 if 判断会写成 2 * nums[premax] == nums[max]，这就会导致出错。
② i 取值的问题
如 nums[2] = {2,0}，有些人习惯 i = 0，从第一个开始遍历，实际上这一步自己与自己比较是没有意义的，虽然 i = 1 在这里几乎对时间复杂度没作用，这是因为这个循环内的语句时间复杂度小，如果是循环内比较复杂，那这一步就比较重要了。
在这里 i = 0 不仅仅是时间复杂度的问题，如果循环内的 else if 语句没有 i != max 判断，程序执行过程中则会将 0 赋值给 premax，这时 max 和 premax 就指向同一个数了，这明显不合理，在后面的判断也可以看出，后面判断 2 * nums[premax] <= nums[max] 不成立，则返回 -1 出错。
改进有两种方法，一种是在循环内 else if 判断加一个 i != max，第二种是 i = 1.
（2）第一种方法的优化（指代码长短上），时间复杂度依旧 O(n)，空间复杂度 O(1)2、只有一个元素的情况
如果数组只有一个元素，比如 nums[1] = {1}，如果没有开始位置的 if(len == 1) 判断，而定义的 premax = 1，那 nums[1] 就会出现访问溢出。
因为这是优化，如果懂了第一种方法，这种也就不用多说。
class Solution {
public:
int dominantIndex(vector& nums)
{
//两个变量：最大数、最大数下标
int m = 0,ans = -1;
//数组长度
int len = nums.size();
//遍历计数器
int i = 0;
while(i < len)
{
//当前数是当前最大数的两倍以上，说明找到了更大的符合要求的最大数，更新当前最大数下标
if(nums[i] >= m * 2) ans = i;
//有两种情况：
//一种是，当前数比当前最大数小，这里又有两种情况：一种是当前数比当前最大数小很多，也就是依旧满足当前最大数比其余数大两倍以上，不会执行下面的语句；另一种是当前数比当前最大数小点，也就是说当前数两倍要比当前最大数大，也就不满足当前最大数比其余数大两倍以上，则最大数下标变为 -1
//一种是，当前数比当前最大数大，但没有大很多，所以不满足大于其两倍，也就不满足题目要求，不存在比其余数大两倍以上的符合要求的最大数
else if(nums[i] * 2 > m) ans = -1;
//上面已经判断了符合要求的问题，因为后面可能还有数要比较，则不管 nums[i] 是否符合要求都要更新一下最大数，如果 nums[i] 比当前最大数大，则更新最大数为 nums[i]，否则保持是 m 不变
m = max(nums[i++],m);
}
return ans;
}
};
（3）傻瓜遍历式（仅思路）
通过一个循环找到最大数及其标，然后再一个循环遍历每个数，判断其是否两倍大于最大数，如果是则返回最大值下标，否则知道循环结束返回 -1。
这种方法看看就行了吧，新手可以练一练手。
所有排序算法都可以用，不过只是为了训练熟悉排序算法就这样做，要真正考虑效率的话还是简单模拟最快。
思路都一致（不指算法本身）：首先在原排序算法代码基础上加上一个变量记录最大数下标（因为排序后位置都改变了，所以要记录最大数原始位置下标），将数组排为升序（降序也行），如果是升序数组，则判断数组第一个和第二个数的大小关系，若第一个数是第二个数的两倍还多，则返回排序时记录下来的最大值下标，否则返回 -1（降序数组反之）。
