7.2 brush two questions

The maximum product of three numbers

628. The maximum product of three numbers

Sort

After sorting, process according to the situation

1. When all numbers are negative or positive , We just choose the largest last three digits to multiply .
2. When there is only one negative number - Directly multiply the last three digits .
3. When there are negative numbers but there are still three positive numbers . There are two cases, the largest of which is .
   1. Multiply the minimum value of two negative numbers by the maximum value of an integer
   2. Multiply by three integers
4. When there are too many negative numbers to have three integer positive numbers
   1. Multiply the minimum value of two negative numbers by the maximum value of an integer

It can be seen from the above situation 3 The situation is the most judged . But the situation is 3 Yes, the maximum value is compatible to 124 So in fact, we only need to judge

• The minimum and minor values in negative numbers ( It is also the overall minimum ) Multiply by the maximum
• Maximum , Second largest value , Multiply next large value

In the above two cases, the value of that case is the largest .

class Solution {
    
public:
    int maximumProduct(vector<int>& nums) 
    {
    
        sort(nums.begin(),nums.end());
        int s = nums.size()-1;
        return max(nums[0]*nums[1]*nums[s],nums[s]*nums[s-1]*nums[s-2]);// There are only two cases in which the answer we want can directly return to the maximum .
    }
};

Linear scanning

The idea is similar to the above question, but we don't get the value by sorting , We use linear scanning to get .

class Solution {
    
public:
    int maximumProduct(vector<int>& nums) 
    {
    
        int min1 = INT_MAX,min2 = INT_MAX;//min1 Is the minimum min2 Is the maximum 
        int max1 = INT_MIN,max2 = INT_MIN,max3 = INT_MIN;//max1 Is the maximum value. .....
        for(int i =0;i<nums.size();i++)
        {
    
            if(nums[i]<min1)
            {
    
                min2 = min1;// Give Way min2 It's a small value 
                min1 = nums[i];//min1 Is the minimum 
            }
            else if(nums[i]<min2)
            {
    
                min2 = nums[i];
            }
            if(nums[i]>max1)
            {
    
                max3 = max2;
                max2 = max1;
                max1 = nums[i];
            }
            else if(nums[i]>max2)
            {
    
                max3 = max2;
                max2 = nums[i];
            }
            else if(nums[i]>max3)
            {
    
                max3 = nums[i];
            }
        }
        return max(min1*min2*max1,max1*max2*max3);// Similar to the above idea, but these values do not come from sorting 
    }
};

How many numbers are smaller than the current number

1365. How many numbers are smaller than the current number

Hash thought

Mark it : I haven't learned hashing , The hashing idea of this title is actually that I have said after several times that this is hashing idea, so there is this title

Ideas :

Put the array ( Array 1 And the given array ) Put the number of in another array ( I become an array 2) in , Convert his value into an array 2 The subscript position of , And use arrays 2 Record the number of his appearances .

Then we just need to put the corresponding array 1 Convert the value of to an array 2 in , Add the contents of the subscript in front of the corresponding subscript of array two .

For example, array 1 There are elements in it 8, We just need to put the array 2 Add the first eight subscript values in (0,1,2,3,4,5,6,7).

class Solution {
    
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) 
    {
    
        vector<int> ret(nums.size());
        int arr[101] = {
    0};// Using hash ideas 
        for(int i = 0;i<nums.size();i++)
        {
    
            arr[nums[i]]++;
        }
        for(int i =0;i<nums.size();i++)
        {
    
            int tmp =0;
            for(int j =0;j<nums[i];j++)
            {
    
                tmp += arr[j];
            }
            ret[i] = tmp;
        }
        return ret;
    }
};