LeetCode169. Majority Element(JAVA)
960 ワード
169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than
You may assume that the array is non-empty and the majority element always exist in the array.
考え方:所与の配列には必ずMajority Elementが存在するため、比較方法は比較的簡単で、最も直接的な方法は:ソート(O(nlogn)、中間のそれはきっとMajority Elementで、もう一つの効率はもっと良くて、時間の複雑度はO(n)しかありません.
public class Solution { public int majorityElement(int[] nums) { //方法1:並べ替え //Arrays.sort(nums); //int len = nums.length; //return nums[len/2]; //方法2:遍歴 int majorityE=nums[0]; int count=1;//majorityElementを最初の要素としてカウント1 for(int i=1;i if(nums[i]==majorityE){ count++; }else if(count==0){ majorityE=nums[i]; count++; }else{ count--; } } return majorityE; } }
Given an array of size n, find the majority element. The majority element is the element that appears more than
⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.
考え方:所与の配列には必ずMajority Elementが存在するため、比較方法は比較的簡単で、最も直接的な方法は:ソート(O(nlogn)、中間のそれはきっとMajority Elementで、もう一つの効率はもっと良くて、時間の複雑度はO(n)しかありません.
public class Solution { public int majorityElement(int[] nums) { //方法1:並べ替え //Arrays.sort(nums); //int len = nums.length; //return nums[len/2]; //方法2:遍歴 int majorityE=nums[0]; int count=1;//majorityElementを最初の要素としてカウント1 for(int i=1;i if(nums[i]==majorityE){ count++; }else if(count==0){ majorityE=nums[i]; count++; }else{ count--; } } return majorityE; } }