July training (day 03) - sorting

Preface

         This is a 《 Heroic algorithm Alliance ： Algorithm training 》 The content of , See details ： Knowledge of the planet ： Heroic algorithm Alliance - June training . After joining the planet , You can enjoy the star Lord CSDN Paid column Free reading The rights and interests of .
         Welcome to leave a message in the comment area to express your views , To know everything , can , Form the habit of brushing questions every day , You can also publish high-quality problem-solving reports by yourself , For community appreciation , Attract a wave of core fans .
         I hope you can think for yourself first , If you really have no idea , Let's look at the following algorithm ideas , If you have ideas but can't write them out , You can refer to the code of others in the circle of friends , There's always one for you , Keep an eye on him , Take its advantage , Short supply .
         The content of today's training is ： Sort
         Today's question can be systematic API, You can also write sorting related content by yourself .

One 、 Exercise questions

Topic link	difficulty
912. Sort array	*****
88. Merge two ordered arrays	*****
1037. Effective boomerang	*****
1232. Dotted line	*****

Two 、 Algorithm ideas

1、 Sort array

        （1） Every language has sorting related API, And the basic implementation must be in O(nlogn) Grade , Therefore, the direct call must not timeout , Just use it .
        （2） Of course , This question can be used for you to train yourself to write all kinds of sorting .

class Solution {
    
public:
    vector<int> sortArray(vector<int>& nums) {
    
        sort(nums.begin(), nums.end());
        return nums;
    }
};

2、 Merge two ordered arrays

        （1） All the questions that need to be sorted , Can be used directly C++ Of sort;
        （2） Time saving and labor saving ！

class Solution {
    
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    
        for(int i = 0; i < n; ++i) {
    
            nums1[m+i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};

3、 Effective boomerang

        （1） In fact, there is no need to sort this question , But I showed you how to sort multiple keywords .
        （2） Then we use cross product to calculate the collinearity of three points , Two vectors , The result of cross product is 0, The included angle between them is 0, So first find the vector v01 and v02, Then find the cross product , Judge whether it is 0 that will do .

class Solution {
    
public:
    bool isBoomerang(vector<vector<int>>& points) {
    
        sort(points.begin(), points.end(), 
        [&]( const vector<int>& a, const vector<int>& b) {
    
            if(a[0] == b[0]) {
    
                return a[1] < b[1];
            }
            return a[0] < b[0];
        });
        points[1][0] -= points[0][0];
        points[1][1] -= points[0][1];

        points[2][0] -= points[0][0];
        points[2][1] -= points[0][1];

        return points[1][0]*points[2][1] - points[1][1]*points[2][0] != 0;
    }
};

4、 Dotted line

        （1） This question is the same as the third question , It can also be calculated directly by cross multiplication .

class Solution {
    
public:
    bool checkStraightLine(vector<vector<int>>& points) {
    
        sort(points.begin(), points.end(), 
        [&]( const vector<int>& a, const vector<int>& b) {
    
            if(a[0] == b[0]) {
    
                return a[1] < b[1];
            }
            return a[0] < b[0];
        });
        for(int i = 1; i < points.size(); ++i) {
    
            points[i][0] -= points[0][0];
            points[i][1] -= points[0][1];
        }
        for(int i = 2; i < points.size(); ++i) {
    
            if( points[i-1][0]*points[i][1] != points[i][0]*points[i-1][1] ) {
    
                return false;
            }
        }
        return true;
    }
};