lc.414 第三大的数
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
- C++ 排序 sort(O(nlogn))
sort set assign *max_element
class Solution {
public:int thirdMax(vector<int>& nums) {
int max3 = 0;sort(nums.begin(),nums.end());set<int> s (nums.begin(),nums.end());nums.assign(s.begin(), s.end());if(nums.size() < 3){
max3 =* max_element(nums.begin(),nums.end());}else{
max3=nums[nums.size()-3]; }return max3;}
};
- C++ 排序
class Solution {
public:int thirdMax(vector<int> &nums) {
sort(nums.begin(), nums.end(), greater<>());for (int i = 1, diff = 1; i < nums.size(); ++i) {
if (nums[i] != nums[i - 1] && ++diff == 3) // 此时 nums[i] 就是第三大的数{
return nums[i];}}return nums[0];}
};
- Java 排序
class Solution {
public int thirdMax(int[] nums) {
Arrays.sort(nums);reverse(nums);for (int i = 1, diff = 1; i < nums.length; ++i) {
if (nums[i] != nums[i - 1] && ++diff == 3) {
// 此时 nums[i] 就是第三大的数return nums[i];}}return nums[0];}public void reverse(int[] nums) {
int left = 0, right = nums.length - 1;while (left < right) {
int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}}
}- C++ 有序集合 set O(n)
如果多于三个数 ，保留三个最大的数，返回最小值；
如果小于三个数，返回最大值；
class Solution {
public:int thirdMax(vector<int> &nums) {
set<int> s;for (int num : nums) {
s.insert(num);if (s.size() > 3) {
s.erase(s.begin());}}return s.size() == 3 ? *s.begin() : *s.rbegin();}
};
set ：
begin(); // 返回指向第一个元素的迭代器
end(); // 返回指向迭代器的最末尾处（即最后一个元素的下一个位置）
clear(); // 清除所有元素
count(); // 返回某个值元素的个数
empty(); // 如果集合为空，返回true
equal_range(); //返回集合中与给定值相等的上下限的两个迭代器
erase() //删除集合中的元素
find() //返回一个指向被查找到元素的迭代器
get_allocator() //返回集合的分配器
insert() //在集合中插入元素
lower_bound() //返回指向大于（或等于）某值的第一个元素的迭代器
key_comp() //返回一个用于元素间值比较的函数
max_size() //返回集合能容纳的元素的最大限值
rbegin() //返回指向集合中最后一个元素的反向迭代器
rend() //返回指向集合中第一个元素的反向迭代器
size() //集合中元素的数目
swap() //交换两个集合变量
upper_bound() //返回大于某个值元素的迭代器
value_comp() //返回一个用于比较元素间的值的函数
- Java set
class Solution {
public int thirdMax(int[] nums) {
TreeSet<Integer> s = new TreeSet<Integer>();for (int num : nums) {
s.add(num);if (s.size() > 3) {
s.remove(s.first());}}return s.size() == 3 ? s.first() : s.last();}
}