[数据结构与算法]LeetCode NO.1996游戏中弱角色的数量(sort函数第三参数用法)

很简单的一个思路就是判断,如果双重循环判断就是O(N^2)的时间复杂度,这样势必会很慢

如果想要降低,就要对数据进行处理一下,比如排序 快速排序就是sort()函数,但是这个是一个二维数组就势必要使用第三个参数

so复习一下sort()函数

void sort (RandomAccessIterator first, RandomAccessIterator last,
Compare comp); （1）第一个参数first：是要排序的数组的起始地址。

（2）第二个参数last：是结束的地址（最后一个数据的后一个数据的地址）

（3）第三个参数comp是排序的方法：可以是从升序也可是降序。如果第三个参数不写，则默认的排序方法是从小到大排序。

示例一

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b);
main(){
　　//sort函数第三个参数自己定义，实现从大到小
　　int a[]={45,12,34,77,90,11,2,4,5,55};
　　sort(a,a+10,cmp);
　　for(int i=0;i<10;i++)
　　　　cout<<a[i]<<" ";
}
//自定义函数
bool cmp(int a,int b){
　　return a>b;
　　//返回的是a>b所以是从大到小排序
}

示例二
可以对类或者结构体的某一个变量进行特定的排序

1 #include<iostream>
 2 #include<algorithm>
 3 #include"cstring"
 4 using namespace std;
 5 typedef struct student{
 6 　　char name[20];
 7 　　int math;
 8 　　int english;
 9 }Student;
10 bool cmp(Student a,Student b);
11 main(){
12 　　//先按math从小到大排序，math相等，按english从大到小排序 
13 　　Student a[4]={{"apple",67,89},{"limei",90,56},{"apple",90,99}};
14 　　sort(a,a+3,cmp);
15 　　for(int i=0;i<3;i++)    
16 　　cout<<a[i].name <<" "<<a[i].math <<" "<<a[i].english <<endl;     
17 }
18 bool cmp(Student a,Student b){
19 　　if(a.math >b.math )
20 　　return a.math <b.math ;//按math从小到大排序 
21 　　else if(a.math ==b.math )
22 　　　　　　return a.english>b.english ; //math相等，按endlish从大到小排序23 
24 }

对题目来说

int numberOfWeakCharacters(vector<vector<int>>& properties) 
    {
      sort(properties.begin(), properties.end(), [](const vector<int> & a, const vector<int> & b) {
            return a[0] == b[0] ? (a[1] < b[1]) : (a[0] > b[0]);
        });//将每一行第一个元素从...到...排序sort()函数排序二维数组规则
        
        int maxDef = 0;
        int ans = 0;
        for (auto & p : properties) //p为一个数组
        {
            if (p[1] < maxDef) {ans++;}
            else 
             {maxDef = p[1];}
        }
        return ans;
    }

这里sort()主要是参数的引用以及攻击能力相同值的处理
1.对攻击能力值进行降序处理
2.相同的攻击能力值进行升序
第二点主要是遍历的考虑
默认maxdef=0,如果有比他小的弱角色++(因为是严格讲,所以不能是小于等于)
这个是防御值,我们在遍历的时候已经确定攻击值不大于了