首页 > itarticle > 算法笔记: 力扣#747 至少是其他数字两倍的最大数

算法笔记: 力扣#747 至少是其他数字两倍的最大数

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class (object):
    def dominantIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_val = 0
        sec_max = 0
        idx = -1
        for i, num in enumerate(nums):
            if num > max_val:
                idx, max_val, sec_max = i, num, max_val
            elif num > sec_max:
                sec_max = num
        return idx if max_val >= sec_max*2 else -1

Java 实现

class  {
    public int dominantIndex(int[] nums) {
        int maxVal = 0;
        int secMax = 0;
        int idx = -1;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > maxVal){
                idx = i;
                secMax = maxVal;
                maxVal = nums[i];
            }else if(nums[i] > secMax){
                secMax = nums[i];
            }
        }
        return maxVal >= secMax * 2 ? idx : -1;
    }
}

时间复杂度

O(n).

空间复杂度

O(1).

链接

747. Largest Number At Least Twice of Others
747. 至少是其他数字两倍的最大数
 (English version) Algorithm Notes: Leetcode#747 Largest Number At Least Twice of Others