leetcode169－Majority Element

本文主要是介绍leetcode169－Majority Element，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题目要求数组中最多的那个元素，这道题目的解法比较直观，直接遍历元素也可以有一个很好的时间复杂度。注意这里的遍历要求技巧，我们可以建立一个哨兵元素，并且记录哨兵元素出现的次数，如果遍历到的元素和哨兵元素一样那么次数加1，如果不一样则次数减1，直到次数不大于0的时候说明该哨兵元素暂时不是数组中次数最多的，此时更换哨兵元素为当前遍历到的元素，然后重复即可。注意这里定义次数最多的元素是大于[n/2]的元素，所以最终最多次数的那个元素它对应的次数在经过加减以后肯定是大于1的那个，所以最终的那个哨兵元素就是次数最多的元素

public class majorityElement {public static void main(String[] args) {int[] arr = {2,2,1,1,1,2,2};System.out.println(getMulNum(arr));int[] brr = {2,2,2,4,1};System.out.println(getMulNum(brr));}public static int getMulNum(int[] arr) {int cnt = 1;int data = arr[0];for(int i = 1;i<arr.length;i++) {if(data == arr[i]) {cnt++;} else {cnt--;}if(cnt <= 0) {cnt = 1;data = arr[i];}}return data;}
}

这篇关于leetcode169－Majority Element的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---