剑指 Offer 39. 数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。你可以假设数组是非空的,并且给定的数组总是存在多数元素。
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2🔗题目链接:https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
方法一:排序求中位数
超过数组一半的数,那么进行排序之后,必然会出现在中心位置
class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); int length = nums.length; return length % 2 == 0 ? nums[length / 2 - 1] : nums[length / 2]; } }
方法二:哈希法
维护一个哈希表存储对应数字出现的次数,超过数组一半的即为结果,但这种做法时间复杂度较高
class Solution { public int majorityElement(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for(int num : nums){ int value = map.getOrDefault(num, 0) + 1; map.put(num, value); } int res = 0; for(int key : map.keySet()){ if(map.get(key) > nums.length / 2){ res = key; break; } } return res; } }
方法三:摩尔投票法
其实就是遍历数组,拼消耗,假设当前数为超过一半的数,遇到不同的就-1,相同的就+1,等于0说明当前超过一半的数被消耗完了,设定新的数作为超过一半的数,以此类推,最终剩下的即为结果数
class Solution { public int majorityElement(int[] nums) { int count = 0; //票数 int m = 0; //记录超过一半的数 for(int num : nums){ if(count == 0){ //如果票数为0,就假设当前数为超过一半的数 m = num; } //等于超过一半的数票数就+1,否则-1,当票数为0时就切换 count += num == m ? 1 : -1; } return m; } }
剑指 Offer 66. 构建乘积数组
题目描述
给定一个数组 A[0,1,…,n-1],请构建一个数组 B[0,1,…,n-1],其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
输入: [1,2,3,4,5] 输出: [120,60,40,30,24]🔗题目链接:https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof
思路
整体思路,结果集中任何一个元素 = 其左边所有元素的乘积 * 其右边所有元素的乘积。先循环构建左边的乘积保存在数组b中,再循环构建右边的乘积,并在此过程中乘以左边的乘积保存于数组b中,这道题构建图表更容易理解。
参考题解:(Leetcode K神)https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/
代码实现
class Solution { public int[] constructArr(int[] a) { int length = a.length; if(length == 0){ return new int[length]; } int[] b = new int[length]; b[0] = 1; //累乘当前元素左边的数,b[i-1]中维护前一个数的累乘结果,只需乘以a[i-1]即可 for(int i = 1; i < length; i++){ b[i] = b[i - 1] * a[i - 1]; } //从后往前累乘右边的数存于temp,再与对应的左边相乘 int temp = 1; for(int i = length - 2; i >= 0; i--){ temp *= a[i + 1]; b[i] *= temp; } return b; } }