java中sort降序排序-(每日一题)第二种排序法做题前的思想
发布时间:2023-06-11 09:10 浏览次数:次 作者:佚名
今天就来讲一下第三大的数这题的第二种解法:排序法
做题前的思想:我们要得到第三大的数,那我们就把题目提供的数组从大到小排序,然后从头开始遍历如果能找到三个不同的元素java中sort降序排序,那就意味着第三大的数找到了。
那想到排序的话C++标准库中的sort函数可以帮助我们排序,但是它是从小到大排的,那我们就用降序排列,也及时从大到小排序。那现在排完序之后我们从头开始遍历,当第一个数与后面一个数不同时,计数器+1java中sort降序排序,意味着我们已经找到了两个不同的数;那只要计数器等于2,也就意味着这时候也就是已经找到三个不同的数了,那么这时返回这个数后面那个数就行啦(这边可能比较难理解,我下面会举个例子)
接下来就是把文字转换成代码了:
#include
#include
#include
using namespace std;
int thirdMax(vector& nums)
{
sort(nums.begin(),nums.end(),greater());//这里的greater作为sort的第三个参数,作用是使原来为升序的sort排序变为降序
int n = nums.size();
int cnt = 0;//新建一个计数器
for (int i = 0; i < n-1; i++)
{
if(nums[i] != nums[i+1]) cnt++;//如果前后两数不相同,则计数器+1
if(cnt == 2) return nums[i+1];//若计数器=2,则已经找到了三个不同的数,返回当前数后一个数
//(下面会举例)
}
return nums[0];//这里意思是:如果上面i到不了2,也就代表着只有两个不同的数值,那么就返回最大值
}
//下面是测试样例
int main() {
vector nums = {3, 1, 3, 5, 5};
int ans = thirdMax(nums);
cout << "The third maximum number is: " << ans << endl;
return 0;
}
以测试样例 数组{3,1,3,5,5} 为例,
首先先被sort倒序排序变为{5,5,3,3,1};
然后 变量i 开始遍历:
nums[0] 和nums[1]相同,i++变为1;nums[1] 和nums[2]分别为5和3,不同,计数器cnt+1=1,i++变为2;nums[2] 和nums[3]分别为3和3,相同,计数器cnt不变,i++变为3;nums[3] 和nums[4]分别为3和1,不同,计数器cnt+1=2,返回nums[4](此时i=3,nums[i+1]就是nums[4])
然后就结束力!