算法刷题日志 hot100 数组分类

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;
    }
}