169Majority Element [LeetCode Java实现]

题目链接：majority-element

/** * 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. * */public class MajorityElement {//40 / 40 test cases passed.//Status: Accepted//Runtime: 253 ms//Submitted: 1 minute ago//时间复杂度为 O(n), 空间复杂度为 O(1)//由于最多的那个元素占一半及以上， 故可以和别的元素相互抵消，最后剩下的未抵消掉的元素为所求//将数组分成三块：num[0…i]为 归并的 还未抵消的数组， num[i+1…j－1]空闲区， num[j…num.length-1]为等待抵消的数组//抵消规则：若num[i] = num[j] 则把num[j]归入num[0…i+1]数组中// 若num[i] != num[j] 则把num[i] 抵消掉 然后 i－－static int majorityElement(int[] num) {int i = -1;for (int j = 0; j < num.length; j++) {if(i == -1) num[++i] = num[j];else {if(num[j] == num[i]) num[ ++i] = num[j];else i –;}}return num[0];}public static void main(String[] args) {System.out.println(majorityElement(new int[]{4}));System.out.println(majorityElement(new int[]{4, 4, 5}));System.out.println(majorityElement(new int[]{4, 3, 3}));System.out.println(majorityElement(new int[]{4, 3, 4}));}}

，生气是拿别人做错的事来惩罚自己