郑州给公司做网站的公司,软件应用与开发,企业网站开发合同,游戏网站织梦模板169. 多数元素
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。 示例 1#xff1a;
输入#xff1a;nums [3,2,3]
输出…
169. 多数元素
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。 示例 1
输入nums [3,2,3]
输出3
示例 2
输入nums [2,2,1,1,1,2,2]
输出2提示
n nums.length1 n 5 * 104-109 nums[i] 109 进阶尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
1、排序法 public static int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];
}
2、摩尔计数
class Solution {public int majorityElement(int[] nums) {int count1,temp nums[0];for (int i 1; i nums.length; i) {if(count0) {temp nums[i];}if(temp nums[i]) {count;}else {count--;}}return temp;}
} 候选人(cand_num)初始化为 nums[0]票数 count 初始化为 1。当遇到与 cand_num 相同的数则票数 count count 1否则票数 count count - 1。当票数 count 为 0 时更换候选人并将票数 count 重置为 1。遍历完数组后cand_num 即为最终答案。 为何这行得通呢 投票法是遇到相同的则 票数 1遇到不同的则 票数 - 1。且“多数元素”的个数 ⌊ n/2 ⌋其余元素的个数总和 ⌊ n/2 ⌋。因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 1。这就相当于每个 “多数元素” 和其他元素 两两相互抵消抵消到最后肯定还剩余 至少1个 “多数元素”。
