首页 > itarticle > algorithm notes: leetcode#747 largest number at least twice of others

algorithm notes: leetcode#747 largest number at least twice of others

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

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 implementation

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;
    }
}

Time complexity

O(n).

Space complexity

O(1).

Link

747. Largest Number At Least Twice of Others
(中文版) 算法笔记: 力扣#747 至少是其他数字两倍的最大数