1.1、题目1
剑指 Offer 39. 数组中出现次数超过一半的数字
1.2、解法
万能哈希表,数学方法看到我要吐血。。。
1.3、代码
class Solution {
public int majorityElement(int[] nums) {
HashMap<Integer,Integer> map = new HashMap();
for(int i=0;i<nums.length;i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
if(entry.getValue()>nums.length/2){
return entry.getKey();
}
}
return 0;
}
}
2.1、题目2
剑指 Offer 66. 构建乘积数组
2.2、解法
老规矩,先判断特殊情况。然后针对赋值。这里是通过两个数组来存每个点的左右两侧积,再到最后将他赋值到res数组中
2.3、代码
class Solution {
public int[] constructArr(int[] a) {
int len = a.length;
if (a == null || len == 0) return a;
int []res=new int[len];
int []right = new int [len];
int []left = new int [len];
left[0]=1;right[len-1]=1;
for(int i=1;i<len;i++){
left[i]=left[i-1]*a[i-1];
right[len-i-1]=right[len-i]*a[len-i];
}
for(int i=0;i<len;i++) res[i]=left[i]*right[i];
return res;
}
}