专栏首页chenjx85的技术专栏leetcode-747-Largest Number At Least Twice of Others(求vector的最大值和次大值)

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

题目描述:

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:

  1. nums will have a length in the range [1, 50].
  2. 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。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-55-跳跃游戏

    1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

    chenjx85
  • leetcode-665-Non-decreasing Array

    chenjx85
  • leetcode-628-Maximum Product of Three Numbers

    chenjx85
  • 双指针法:一样的道理,能解决四数之和

    题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c ...

    代码随想录
  • 漫画:经典鹅厂面试题(4sum - nSum)

    第18题:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + ...

    程序员小浩
  • LeetCode-15 三数之和

    今天我们学习第15题三数之和,这是一道中等题。像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们看看这道题...

    用户3470542
  • LeetCode-18 四数之和

    今天我们学习第18题四数之和,这是一道中等题。像这样数组的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们看看这道题的...

    用户3470542
  • python(leetcode)-1.两

    分析原因:代码两层for循环,时间复杂度为O(n^2),所以遇到数据量大的情况耗时较久。

    py3study
  • Python3刷题系列(三)

    中文版:https://leetcode-cn.com/problems/sqrtx/

    用户5473628
  • leetcode-55-跳跃游戏

    1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

    chenjx85

扫码关注云+社区

领取腾讯云代金券