LC 747. 至少是其他数字两倍的最大数

题目描述

这是 LeetCode 上的 747. 至少是其他数字两倍的最大数 ，难度为简单。

给你一个整数数组 $nums$ ，其中总是存在 唯一的 一个最大整数。

请你找出数组中的最大元素并检查它是否至少是数组中每个其他数字的两倍。

如果是，则返回 最大元素的下标 ，否则返回 $-1$ 。

示例 1：

输入：nums = [3,6,1,0]

输出：1

解释：6 是最大的整数，对于数组中的其他整数，6 大于数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。

示例 2：

1
2
3

输入：nums = [1,2,3,4]
输出：-1
解释：4 没有超过 3 的两倍大，所以返回 -1 。

示例 3：

输入：nums = [1]

输出：0

解释：因为不存在其他数字，所以认为现有数字 1 至少是其他数字的两倍。

提示：

$1 <= nums.length <= 50$
$0 <= nums[i] <= 100$
$nums$ 中的最大元素是唯一的

模拟

根据题意进行模拟即可，遍历过程中维护最大值和次大值的下标，最后判断最大值是否至少为次大值两倍。

然后？今天属于圆梦了？（这真的只是他们的日常可爱 🤣

代码（感谢 @5cm/s 🌸、@Benhao 和 @Qian 几位总提供的其他语言版本 🤣 🤣 ）：

class Solution {
    public int dominantIndex(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;
        int a = -1, b = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[b]) {
                a = b; b = i;
            } else if (a == -1 || nums[i] > nums[a]) {
                a = i;
            }
        }
        return nums[b] >= nums[a] * 2 ? b : -1;
    }
}

class Solution(object):
    def dominantIndex(self, nums):
        n = len(nums)
        if n == 1:
            return 0
        a, b = -1, 0
        for i in range(1, n):
            if nums[i] > nums[b]:
                a, b = b, i
            elif a == -1 or nums[i] > nums[a]:
                a = i
        return b if nums[b] >= nums[a] * 2 else -1

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        a, b = -1, 0
        for i in range(1, n):
            if nums[i] > nums[b]:
                a, b = b, i
            elif a == -1 or nums[i] > nums[a]:
                a = i
        return b if nums[b] >= nums[a] * 2 else -1

func dominantIndex(nums []int) int {
    n := len(nums)
    if n == 1{
        return 0
    }
    a, b := -1, 0
    for i := 1; i < n; i++ {
        if nums[i] > nums[b] {
            a, b = b, i
        } else if a == -1 || nums[i] > nums[a] {
            a = i
        }
    }
    if nums[b] >= nums[a] * 2{
        return b
    }
    return -1
}

impl Solution {
    pub fn dominant_index(nums: Vec<i32>) -> i32 {
        let mut mx = 0;
        let mut ans = -1 as i32;
        for i in 0..nums.len() {
            if nums[i] >= mx * 2 {
                ans = i as i32;
            }
            else if nums[i] * 2 > mx {
                ans = -1 as i32;
            }
            if nums[i] > mx {
                mx = nums[i];
            }
        }
        ans
    }
}

int dominantIndex(int* nums, int numsSize){
    if(numsSize == 1) return 0;
    int a = -1, b = 0;
    for(int i = 1; i < numsSize; i++){
        if (nums[i] > nums[b]) {
            a = b; b = i;
        } else if (a == -1 || nums[i] > nums[a]) {
            a = i;
        }
    }
    return nums[b] >= nums[a] * 2 ? b : -1;
}

public class Solution {
    public int DominantIndex(int[] nums) {
        int n = nums.Length;
        if (n == 1) return 0;
        int a = -1, b = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[b]) {
                a = b; b = i;
            } else if (a == -1 || nums[i] > nums[a]) {
                a = i;
            }
        }
        return nums[b] >= nums[a] * 2 ? b : -1;
    }
}

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int mx = 0, ans = -1;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] >= mx * 2) ans = i;
            else if (nums[i] * 2 > mx) ans = -1;
            mx = max(nums[i], mx);
        }
        return ans;
    }
};

var dominantIndex = function(nums) {
    const n = nums.length
    if(n == 1) return 0
    let a = -1, b = 0
    for (let i = 1; i < n; i++){
        if (nums[i] > nums[b]) {
            a = b; b = i;
        } else if (a == -1 || nums[i] > nums[a]) {
            a = i;
        }
    }
    return nums[b] >= nums[a] * 2 ? b : -1;
};

function dominantIndex(nums: number[]): number {
    const n = nums.length
    if(n == 1) return 0
    let a = -1, b = 0
    for (let i = 1; i < n; i++){
        if (nums[i] > nums[b]) {
            a = b; b = i;
        } else if (a == -1 || nums[i] > nums[a]) {
            a = i;
        }
    }
    return nums[b] >= nums[a] * 2 ? b : -1;
};

class Solution {
    function dominantIndex($nums) {
        $n = sizeof($nums);
        if ($n == 1) return 0;
        $a = -1; $b = 0;
        for ($i = 1; $i < $n; $i++) {
            if ($nums[$i] > $nums[$b]) {
                $a = $b;
                $b = $i;
            } else if ($a == -1 || $nums[$i] > $nums[$a]) {
                $a = $i;
            }
        }
        if($nums[$b] >= $nums[$a] * 2){
            return $b;
        }
        return -1;
    }
}

class Solution {
    func dominantIndex(_ nums: [Int]) -> Int {
        var n = nums.count
        if n == 1 {
            return 0
        }
        var (a, b) = (-1, 0)
        for i in 1..<nums.count {
            if nums[i] > nums[b] {
                (a, b) = (b, i)
            }
            else if a == -1 || nums[i] > nums[a] {
                a = i
            }
        }
        return nums[b] >= nums[a] * 2 ? b : -1
    }
}

class Solution {
    fun dominantIndex(nums: IntArray): Int {
        var mx = 0
        var ans = -1
        for (i in nums.indices) {
            when {
                nums[i] >= mx * 2 -> ans = i
                nums[i] * 2 > mx -> ans = -1
            }
            if (nums[i] > mx) mx = nums[i]
        }
        return ans
    }
}

object Solution {
    def dominantIndex(nums: Array[Int]): Int = {
        var mx = 0
        var ans = -1
        for (i <- 0 to (nums.length - 1)) {
            if (nums(i) >= mx * 2) ans = i
            else if (nums(i) * 2 > mx) ans = -1
            if (nums(i) > mx) mx = nums(i)
        }
        return ans
    }
}

def dominant_index(nums)
    n = nums.length
    return 0 if n == 1
    a = -1
    b = 0
    nums.each_with_index do |num, i|
        next if i == 0
        if nums[i] > nums[b]
            a = b
            b = i
        elsif a.eql?(-1) or nums[i] > nums[a]
            a = i
        end
    end
    return nums[b] >= nums[a] * 2 ? b : -1
end

(define/contract (dominant-index nums)
  (-> (listof exact-integer?) exact-integer?)
  (let loop ([nums nums] [i 0] [mx 0] [ans -1])
    (cond
      [(empty? nums) ans]
      [else
        (define x (car nums))
        (define mxx (max x mx))
        (cond
          [(>= x (* mx 2)) (loop (cdr nums) (+ i 1) mxx i)]
          [(> (* x 2) mx) (loop (cdr nums) (+ i 1) mxx -1)]
          [else (loop (cdr nums) (+ i 1) mxx ans)]
        )
      ]
    )
  )
)

defmodule Solution do
  @spec dominant_index(nums :: [integer]) :: integer
  def dominant_index(nums) do
    solve(nums, 0, -1, 0)
  end
  def solve([], mx, ans, cur) do
    ans
  end
  def solve([x | rest], mx, ans, cur) when x >= mx * 2 do
    solve(rest, max(x, mx), cur, cur + 1)
  end
  def solve([x | rest], mx, ans, cur) when x * 2 > mx do
    solve(rest, max(x, mx), -1, cur + 1)
  end
  def solve([x | rest], mx, ans, cur) do
    solve(rest, max(x, mx), ans, cur + 1)
  end
end

-spec dominant_index(Nums :: [integer()]) -> integer().
dominant_index(Nums) ->
  solve(Nums).

solve(List) ->
  solve(List, 0, -1, 0).
solve([], Max, Ans, Cur) ->
  Ans;
solve([Head|Rest], Max, Ans, Cur) when Head >= Max * 2 ->
  solve(Rest, max(Max, Head), Cur, Cur + 1);
solve([Head|Rest], Max, Ans, Cur) when Head * 2 > Max ->
  solve(Rest, max(Max, Head), -1, Cur + 1);
solve([Head|Rest], Max, Ans, Cur) ->
  solve(Rest, max(Max, Head), Ans, Cur + 1).

max(A, B) when A > B ->
  A;
max(A, B) ->
  B.

时间复杂度：$O(n)$
空间复杂度：$O(1)$

全鱼宴（是全语言这错别字还挺可爱 🤣

经过三位总 @5cm/s 🌸、@Benhao 和 @Qian 的不懈努力，通过举一反三、连蒙带猜，把所有语言弄出了 🤣

这个过程中也有幸见到，如果一个语言只有一份代码，居然界面是这样的（没有时间和内存的分布图：

我和我的小伙伴纷纷表示这样的 Flag 再也不敢了 🤣

最后

这是我们「刷穿 LeetCode」系列文章的第 No.747 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

模拟

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 373. 查找和最小的K对数字上一篇

LC 334. 递增的三元子序列下一篇

LC 747. 至少是其他数字两倍的最大数

题目描述

模拟

全鱼宴（是全语言 这错别字还挺可爱 🤣

最后

全鱼宴（是全语言这错别字还挺可爱 🤣