面试题 17.10. 主要元素

面试题 17.10. 主要元素

截止到目前我已经写了 600多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载下载链接：​​int majorityElement(int[] nums) { //边界条件判断，如果数组为空就返回-1 if (nums == null || nums.length == 0) return -1; //先找出主要元素 int major = nums[0]; int count = 1; for (int i = 1; i < nums.length; i++) { if (major == nums[i]) { //如果当前元素等于major，count就加1 count++; } else { //否则count就减1， count--; if (count < 0) { //如果count小于0，说明前面的 //全部抵消了，这里在重新赋值 major = nums[i]; count = 1; } } } //下面是判断主要元素是否存在 count = 0; int half = nums.length >> 1; for (int num : nums) { if (major == num) if (++count > half) return major; } return -1;}

时间复杂度：​​O(N)​​​，两个​​for​​​循环，不是嵌套的。空间复杂度：​​O(1)​​，使用了两个变量。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。