刷题日记03
难呀，今天这题难呀，直接写的太麻烦了。看了题解发现最容易想出来的方法暴力映射超出了时间限制，其次最容易想出来的是用HashMap做的。
多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
我先复盘一下我自己最初的思路，我是这么想的，先进行排序，得到升序序列[1,1,1,2,2,2,2]。然后我定义一个Set和一个List分别为set和list，再定义一个计数变量count = 1。遍历数组，假如当前元素a[i]和后一个元素a[i+1]相等，我就在Set中存放a[i]，因为这说明a[i]这个数不止一个，是一个潜在的多数，因此要把计数count加1。这里用Set是因为其不能存储重复元素，即使add()了重复元素对Set集合也不产生改变，所以Set的作用就是存储出现次数大于1的元素。
注意的是这个Set必须是LinkedHashSet，因为这种Set元素的排序是按照存入顺序排列的，我原来就是用HashSet，但我发现有时候输出结果不对，调试的时候就发现是因为set和list没对应上，就是因为set的顺序不对。
如果a[i] != a[i+1]，就说明a[i]这个数以及计数完毕，下一个新的数来了，就需要先判断count是否大于1，如果大于1就说明上一个数出现多次，就要把出现次数count存储到集合list中，然后再把count复原，开始记录下一个数。
for (int i = 0; i < nums.length - 1; i++) {
if(nums[i] == nums[i+1]){
set.add(nums[i]);
count++;
}else {
//先判断count是否等于1，如果不等于1，说明这个nums[i]出现了超过一次，就需要把出现次数
//存储到list2中，然后复原count
if (count != 1){
list.add(count);
count = 1;
}
}
}
list.add(count);
这么写最坑的就是我最后还要写一句list.add(count)，因为不写的话，例如[1,1,1,2,2,2,2]这样的，最后这个2的count无法存入到list中，是因为遍历索引的问题，看看有没有大神能够帮我优化一下。然后执行下面代码，找到了题目要求的多数
Integer max = Collections.max(list); int index = list.indexOf(max); List<Integer> setlist = new ArrayList<>(set); Integer result = setlist.get(index);
我排序代码这次用的是归并，上次用的是快速，把之前学的高级排序都复习复习。下面是我整体代码
class Solution {
private static int[] assist;
public int majorityElement(int[] nums) {
sort(nums);
//用来存储nums中出现的次数超过1次的元素
Set<Integer> set = new LinkedHashSet<>();
//List<Integer> list1 = new ArrayList<>();
//用来存储nums中出现的次数超过1次的元素的个数，和arr1对应
List<Integer> list = new ArrayList<>();
//计数，用来计nums中不出现的次数超过1次的元素的个数，然后存在arr2中
int count = 1;
if (nums.length == 1){
return nums[0];
}
//遍历nums数组
for (int i = 0; i < nums.length - 1; i++) {
if(nums[i] == nums[i+1]){
set.add(nums[i]);
count++;
}else {
//先判断count是否等于1，如果不等于1，说明这个nums[i]出现了超过一次，就需要把出现次数
//存储到list2中，然后复原count
if (count != 1){
list.add(count);
count = 1;
}
}
}
list.add(count);
System.out.println(set);
System.out.println(list);
Integer max = Collections.max(list);
int index = list.indexOf(max);
List<Integer> setlist = new ArrayList<>(set);
Integer result = setlist.get(index);
System.out.println(result);
return result;
}
//排序
public static void sort(int[] nums){
assist = new int[nums.length];
int lo = 0;
int hi = nums.length - 1;
sort(nums,lo,hi);
}
//范围内排序
public static void sort(int[] nums,int lo,int hi){
if (lo >= hi){
return;
}
int mid = lo + (hi - lo)/2;
sort(nums,lo,mid);
sort(nums,mid+1,hi);
//归并
merge(nums,lo,mid,hi);
}
/*
归并，lo到mid一组，mid+1到hi一组，对这两组数据进行合并
*/
public static void merge(int[] num,int lo,int mid,int hi){
//lo到mid数组和mid+1hi数组归并到assist辅助数组中
int i = lo;//assist的指针，从头开始
int p1 = lo;//左数组指针第一个元素
int p2 = mid + 1;//右数组指针第一个元素
//比较左右两个数组元素大小，哪个小就把哪个数存入到assist中
while (p1 <= mid && p2 <= hi){
if(less(num[p1],num[p2])){
assist[i++] = num[p1++];
}else {
assist[i++] = num[p2++];
}
}
//在一边数组全部填充好了之后就可填充另一个
while (p1 <= mid){
assist[i++] = num[p1++];
}
while (p2 <= hi){
assist[i++] = num[p2++];
}
//拷贝
for (int j = lo;j <= hi;j++){
num[j] = assist[j];
}
}
//比较大小
public static boolean less(Integer v,Integer w){
return v.compareTo(w) < 0;
}
//交换
public static void exch(int[] a,int i,int j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
根据此题题解，我知道可以用HashMap来做，键用来存数字，值用来存出现的次数。如果第一个元素是2，我们就可以去集合中看看这个2是否存在，如果不存在，是第一次出现，就往集合中添加2和1就行，表示2出现了1次了。如果第二元素也是2，还要去集合中判断一下，已经存在了，把值加1，以此类推。把所有数字以及出现次数都存入到HashMap中后，进行遍历，得到max，用打擂台的方式。最后再进行一次遍历，找到max对应的键。即为出现最多的数字。附上找最大值的代码，排序方法同上。
public int majorityElement(int[] nums) {
sort(nums);
HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if(hashMap.containsKey(nums[i])){
//如果这个键已经存在，就把之前的值取出来然后加一
int count = hashMap.get(nums[i]);
count++;
hashMap.put(nums[i],count);
}else {
//这个数不存在，添加进入作为键，值就是1
hashMap.put(nums[i],1);
}
}
//设最大值为0
int max = 0;
//遍历map，找出最大值
Set<Map.Entry<Integer, Integer>> entries = hashMap.entrySet();
for (Map.Entry<Integer, Integer> entry : entries) {
int value = entry.getValue();
if (value > max){
max = value;
}
}
System.out.println(hashMap);
System.out.println(max);
//找到最大值对应的键
Integer key = 0;
for (Map.Entry<Integer, Integer> entry : entries) {
int value = entry.getValue();
if(value == max){
key = entry.getKey();
}
}
return key;
}
这题真是花费我好久时间，先把自己想的整出来了，再去学学Map，不过收获颇丰，不枉我花费时间。
#你们的毕业论文什么进度了##你觉得一个人能同时学好硬件和软件吗##你的秋招进展怎么样了##我的求职思考##你觉得今年秋招难吗#
华为二面45人在聊