网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 747. 至少是其他数字两倍的最大数 ，难度为 简单。
Tag : 「模拟」
给你一个整数数组 numsnums ，其中总是存在 唯一的 一个最大整数 。
请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。
如果是，则返回 最大元素的下标 ，否则返回 -1−1 。
示例 1：
输入：nums = [3,6,1,0] 输出：1 解释：6 是最大的整数，对于数组中的其他整数，6 大于数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。 复制代码
示例 2：
输入：nums = [1,2,3,4] 输出：-1 解释：4 没有超过 3 的两倍大，所以返回 -1 。 复制代码
示例 3：
输入：nums = [1] 输出：0 解释：因为不存在其他数字，所以认为现有数字 1 至少是其他数字的两倍。 复制代码
提示：
- 1 <= nums.length <= 501<=nums.length<=50
- 0 <= nums[i] <= 1000<=nums[i]<=100
- numsnums 中的最大元素是唯一的
模拟
根据题意进行模拟即可，遍历过程中维护最大值和次大值的下标，最后判断最大值是否至少为次大值两倍。
然后？今天属于圆梦了？（这真的只是他们的日常可爱 🤣
网络异常，图片无法展示
|
代码（感谢 @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(n)
- 空间复杂度：O(1)O(1)
全鱼宴（是全语言 这错别字还挺可爱 🤣
经过三位总 @5cm/s 🌸、@Benhao 和 @Qian 的不懈努力，通过举一反三、连蒙带猜，把所有语言弄出了 🤣
这个过程中也有幸见到，如果一个语言只有一份代码，居然界面是这样的（没有时间和内存的分布图：
网络异常，图片无法展示
|
我和我的小伙伴纷纷表示这样的 Flag 再也不敢了 🤣
最后
这是我们「刷穿 LeetCode」系列文章的第 No.747 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
