个人网站取什么域名好,网站编程设计如何写备注,网页微信版官方,定制app开发 杭州app开发公司题目#xff1a;
给定一个大小为 n 的数组nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 n/2 的元素。你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
示例#xff1a;
输入#xff1a;nums [3,2,3]
输出#xff1a;…题目
给定一个大小为 n 的数组nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 n/2 的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例
输入nums [3,2,3]
输出3实现
1. main方法
public static void main(String[] args) {int[] nums {2,2,1,1,1,2,2};//方式一method1(nums);//方式二method2(nums);//方式三摩尔投票法method3(nums);
}2. 方式一
/*** 方式一排序取中间值即可*/
private static int method1(int[] nums) {// 方式一排序取中间值即可Arrays.sort(nums);System.out.println(way1: nums[nums.length / 2]);return nums[nums.length / 2];
}原理
使用排序大于n.length/2 的必定在最中间
3. 方式二
/*** 方式二使用HashMap实现*/
private static int method2(int[] nums) {// 使用HashMap实现MapInteger, Integer map new HashMap();// 遍历数组将数组中的元素作为key出现的次数作为valuefor (int num : nums) {Integer count map.get(num);if (count null) {count 0;}map.put(num, count);if (count nums.length / 2) {System.out.println(way2: num);return num;}}// 如果没有找到返回-1return -1;
}原理
使用Hashmap实现key为值value为次数value大于nums.length / 2就找到并返回
3. 方式三
/*** 摩尔投票法-核心就是对拼消耗* 这想法真的是太妙了而且还是一次遍历就解决了而且空间复杂度还是O(1)。* param nums* return*/private static int method3(int[] nums) {// 摩尔投票法-核心就是对拼消耗int count 0;int candidate 0;for (int num : nums) {if (count 0) {candidate num;}count (num candidate) ? 1 : -1;}System.out.println(way3: candidate);return candidate;}原理
使用的是摩尔投票法核心就是对拼消耗
