文章目录
- [169. 多数元素](https://leetcode.cn/problems/majority-element/)
- 旋转图像
- 215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/description/)
- 238. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/)
169. 多数元素
运用了摩尔投票的思想，就是cnt就是票数，当票数为0的时候可以缩小区间，且此时不影响众数的取值
class Solution {public int majorityElement(int[] nums) {int ans = nums[0],cnt = 1;for(int i=1;i<nums.length;i++){if(ans==nums[i]){cnt++;}else if(--cnt == 0){ans = nums[i];cnt=1;}}return ans;}
}
旋转图像
记住i 是每一行 j是每一列 然后此解法是原地旋转90°
class Solution {public void rotate(int[][] matrix) {int n = matrix.length;for(int i=0;i<n/2;i++){for(int j=0;j<(n+1)/2;j++){int tmp = matrix[i][j];matrix[i][j]=matrix[n-1-j][i];matrix[n-1-j][i]=matrix[n-1-i][n-1-j];matrix[n-1-i][n-1-j]=matrix[j][n-1-i];matrix[j][n-1-i]=tmp;}}}
}
[
215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/description/)
将数组排序，排序之后，随机整一个随机数在该数组的范围里面，
class Solution {public int findKthLargest(int[] nums, int k) {List<Integer> list = new ArrayList<>();for(int num : nums){list.add(num);}return quickSelect(list,k);}public int quickSelect(List<Integer>list,int k ){Random rand = new Random();int ans = list.get(rand.nextInt(list.size()));List<Integer> small = new ArrayList<Integer>();List<Integer> big = new ArrayList<>();List<Integer> equal = new ArrayList<>();for(int num:list){if(num<ans ){small.add(num);}else if(num >ans ){big.add(num);}else{equal.add(num); }}if(k<=big.size()){return quickSelect(big,k);}if(big.size()+equal.size()<k){return quickSelect(small,k-(equal.size()+big.size()));}return ans;}
}
[
238. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/)
1 2 3 4
1 1 3 4
1 2 1 4
1 2 3 1 比如数组为 1234，则答案则像左边的矩阵一样，然后中间线就是1 然后就分为左下角，和右上角，
class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int [] ans = new int [n];ans[0]=1;int tmp = 1;for(int i=1;i<n;i++){ans[i]=ans[i-1]*nums[i-1];}for(int i=n-2;i>=0;i--){tmp *= nums[i+1];ans[i] *= tmp;}return ans;}
}
