(七)行列の中の共通数を探すアルゴリズム
Gven an array of size n,find the majority element.The majority element is the element that appars モーニング
You may asome that the array is non-empty and the majority element always exist in the array.
PS:タイトルの中で恥知らずな要求の共通数の基準は出現回数が配列長さの半分より大きい数で、しかもこの数字が必ず存在すると仮定します.
======================================================================================================================================
以下は簡単なロジックです.
一、まず配列を並べ替える
二、第一の数が中間の数と等しいと判断したら、衆数は第一の数となり、最後の数と中間の数が等しいと、衆数は最後の数となり、そうでなければ、衆数は中間の数となる.
⌊ n/2 ⌋
times.You may asome that the array is non-empty and the majority element always exist in the array.
PS:タイトルの中で恥知らずな要求の共通数の基準は出現回数が配列長さの半分より大きい数で、しかもこの数字が必ず存在すると仮定します.
======================================================================================================================================
以下は簡単なロジックです.
一、まず配列を並べ替える
二、第一の数が中間の数と等しいと判断したら、衆数は第一の数となり、最後の数と中間の数が等しいと、衆数は最後の数となり、そうでなければ、衆数は中間の数となる.
public class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
if (nums[0] == nums[len / 2]) {
return nums[0];
} else if (nums[len-1] == nums[len / 2]) {
return nums[len - 1];
} else {
return nums[len / 2];
}
}
}