leetcode-747-Largest Number At Least Twice of Others（求vector的最大值和次大值）

chenjx85

发布于 2018-05-21 18:22:30

6700

发布于 2018-05-21 18:22:30

文章被收录于专栏：chenjx85的技术专栏chenjx85的技术专栏

题目描述：

In a given integer array nums, there is always exactly one largest element.

Find whether the largest element in the array is at least twice as much as every other number in the array.

If it is, return the index of the largest element, otherwise return -1.

Example 1:

Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x.  The index of value 6 is 1, so we return 1.

Example 2:

Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.

Note:

nums will have a length in the range [1, 50].
Every nums[i] will be an integer in the range [0, 99].

要完成的函数：

int dominantIndex(vector<int>& nums)

说明：

给定一个vector，要求判断这个vector中的最大值是不是至少等于其他所有元素值的两倍，如果是的话，返回最大值的位置，如果不是，返回-1。

这道题其实相当容易，就是求vector的最大值和次大值，以及在求最大值的过程中记录一下最大值的位置。

我们考虑一下边界条件，只有一个元素和只有两个元素的情况，接着构造一般情况下的代码，如下：

　　 int dominantIndex(vector<int>& nums) 
    {
        int s1=nums.size();
        if(s1==1)//只有一个元素的边界条件
            return 0;
        else if(s1==2)//只有两个元素的边界条件
        {
            if(nums[0]>nums[1])
            {
                if(nums[0]>=2*nums[1])
                    return 0;
                else
                    return -1;
            }
            else
            {
                if(nums[1]>=2*nums[0])
                    return 1;
                else
                    return -1;
            }
        }
        int max1,max2,i=2,index;
        if(nums[0]>=nums[1])
        {
            max1=nums[0];
            max2=nums[1];
            index=0;
        }
        else
        {
            max1=nums[1];
            max2=nums[0];
            index=1;
        }
        while(i<s1)//i从2开始
        {
            if(nums[i]>=max1)
            {
                max2=max1;
                max1=nums[i];
                index=i;
            }
            else
            {
                if(nums[i]>=max2)
                    max2=nums[i];
            }
            i++;
        }
        if(max1>=2*max2)
            return index;
        else
            return -1;
    }

上述代码虽然条件判断语句多了点，但大体上来看没有浪费很多时间，代码也不难理解。

实测9ms，beats 81.63% of cpp submissions。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-05-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

element