# LeetCode Easy 747. Largest Number At Least Twice of Others

tags: leetcode

問題

• Explore
• Problems

アイデア

配列の中で最も大きな要素が他のどの要素よりも少なくとも2倍はあるかどうか探せ．あれば，そのindexを，なければ-1を返せという問題です．

最も大きな数を変数に格納すれば良いです．

配列の大きさは[1, 50]であり，1のときは1を返せば良いようです．

解法

最大数とその添え字を記憶し，配列を走査して条件を満たさなければ-1を返し，全ての要素で条件を満たしていれば添字を返します．

計算量

配列の要素数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

C++

class Solution {
public:
  int dominantIndex(vector<int>& nums) {
    auto largest = max_element(nums.begin(), nums.end());
    for (auto iter = nums.begin(); iter != nums.end(); ++iter)
      if (*largest < 2 * *iter && largest != iter)
        return -1;
    return distance(nums.begin(), largest);
  }
};