May brush question 01 - array

Today's brush topic content ： Array

Preface

• An algorithm opens the way to brush the questions of waste materials , Update the problem solution content of the problem brush every day
• Focus on personal understanding , Look at the difficulty and update the number of questions
• The title comes from Li Kou
• New column , Try to work out at least one question every day =v=
• Language java、python、c\c++

---

One 、 Today's topic

1. 2016. The maximum difference between incremental elements
2. 2239. Find the closest to 0 The number of
3. 1475. The final price after discount
4. 2248. Intersection of multiple arrays

Two 、 Their thinking

1. 2016. The maximum difference between incremental elements

1. According to the requirements of the topic is to find the minimum value of the preceding subscript and the maximum value of the difference between the following subscript
2. Use a variable to record the minimum value of the preceding item
3. Maintain the minimum value variable and update the difference

class Solution {
    
    public int maximumDifference(int[] nums) {
    
        int i = 0;
        int j = 1;
        int n = nums.length;
        int ret  = - 1;
        int pre = nums[0];
        while(j < n){
    
            if(nums[j] > pre){
    
                ret = Math.max(ret, nums[j] - pre);
            }else{
    
                pre = nums[j];
            }
            j++;
        }
        return ret;
    }
}

---

2. 2239. Find the closest to 0 The number of

1. To find the closest 0 Number of numbers , Is to find the number with the smallest absolute value
2. When the absolute value is the same, take a larger number
3. Use two variables to maintain absolute value and true value

class Solution {
    
    public int findClosestNumber(int[] nums) {
    
            int real = nums[0];
            int absval = Math.abs(nums[0]);
            for (int n: nums){
    
                int x = Math.abs(n);
                //  The absolute value of the current number is smaller than the recorded value 
                if (x < absval){
    
                    absval = x;
                    real = n; 
                }
                //  The absolute value of the current number is the same 
                else if(x == absval){
    
                    real = real > n ? real: n;  //  The truth value takes the greater value 
                }
                
            }
            return real;
    }
}

---

3. 1475. The final price after discount

1. The value in front of the array subscript can be deducted by the smaller value in the back
2. Just traverse the array , Get the smaller value after the array
3. Just update the array

class Solution {
    
    public int[] finalPrices(int[] prices) {
    
        int i, j;
        int n = prices.length;
        for(i = 0; i < n; i++){
    
            for (j = i+1; j < n; j++){
    
                if (prices[j] <= prices[i]){
    
                    prices[i] -= prices[j];
                    break;
                }
            }
        }
        return prices;
    }
}

---

4. 2248. Intersection of multiple arrays

1. Because the range of numbers is not large , So we can use hash Table to do questions
2. Count the number of all numbers in each array
3. If the number of numbers is the same as the number of arrays, it means that this number is a subset of the intersection

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        length = len(nums)
        ret = [];
        hash_tb = [0] * 1001
        for num in nums:
            for n in num:
                hash_tb[n] += 1
        for idx, val in enumerate(hash_tb):
            if val == length:
                ret.append(idx)
        return ret