Leetcode ―トップインタビュー―。多数派要素

次のような簡単な問題です:

サイズ n の配列 nums を指定すると、多数決の要素を返します。

多数派要素とは、⌊n / 2⌋ 回以上出現する要素です。大部分の要素が常に配列内に存在すると仮定することができます。

例 1:

入力: nums = [3,2,3]
出力: 3

例 2:

入力: nums = [2,2,1,1,1,2,2]
出力: 2

制約:

n == nums.length
1 -109

一見すると、地図を作成してから、最もよく表示される地図を集めることを考えるでしょう。

よく考えたら、並べ替えて最も多く表示されるものを取得できればそれで十分です。

そして、さらに簡単な方法があります。説明を注意深く読めば、多数要素とは、配列の半分以上に出現する要素であることが理解できるでしょう。

それを念頭に置いて、これをソートして中央のインデックスを取得すれば、問題は解決します。

class Solution {
    public int majorityElement(int[] nums) {

        // sort
        Arrays.sort(nums);

        // if by majority element it means that appears more than half of nums size
        // then picking the middle element would be the one that's a majority element
        return nums[nums.length / 2];
    }
}

実行時間: 4 ミリ秒、Majority Element の Java オンライン送信の 54.53% よりも高速です。

メモリ使用量: 53.5 MB、Majority Element の Java オンライン送信の 9.23% 未満。

—

それだけです！他に議論したいことがあれば、お気軽にコメントしてください。何か見逃した場合はお知らせください。適宜更新します。

次の投稿まで！ :)

以上がLeetcode ―トップインタビュー―。多数派要素の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。