堆排序、快速排序
建立哈希表并排序
荷兰国旗问题
leetcode在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
priority_queue
,可以当成一种高级队列,只不过这个队列是已经排好序的。 int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int> > queue;
for (auto it : nums) {
queue.push(it);
if (queue.size() > k) queue.pop();
}
return queue.top();
}
if (left > right) return ;。
int findKthLargest(vector<int>& nums, int k) {
quickSort(nums, 0, nums.size() - 1);
return nums[nums.size() - k];
}
void quickSort(vector<int>& nums, int left, int right) {
if (left > right) return ;
int mid = partition(nums, left, right);
quickSort(nums, left, mid - 1);
quickSort(nums, mid + 1,right);
}
int partition(vector<int>& nums, int left, int right) {
int p = nums[left];
while (left < right) {
while (nums[right] >= p && left < right) right--;
nums[left] = nums[right];
while (nums[left] <= p && left < right) left++;
nums[right] = nums[left];
}
nums[left] = p;
return left;
}
leetcode给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
static bool cmp(pair<int, int> v1, pair<int, int> v2){
return v1.second > v2.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> hash;
for (int i = 0; i < nums.size(); ++i) {
hash[nums[i]]++;
}
vector<pair<int, int> > arr(hash.begin(), hash.end());
sort(arr.begin(), arr.end(), cmp);
vector<int> res;
for(int i = 0; i < k; ++i){
res.push_back(arr[i].first);
}
return res;
}
leetcode 给你一个非空数组,返回此数组中 第三大的数 。如果不存在,则返回数组中最大的数。
class Solution:
def thirdMax(self, nums: List[int]) -> int:
nums.sort(reverse = True)
diff = 1
for i in range(1, len(nums)):
if nums[i] != nums[i-1]:
diff += 1
if diff == 3:
return nums[i]
return nums[0]
from sortedcontainers import SortedList
class Solution:
def thirdMax(self, nums: List[int]) -> int:
s = SortedList()
for num in nums:
if num not in s:
s.add(num)
if len(s) > 3:
s.pop(0)
return s[0] if len(s) == 3 else s[-1]
leetcode给定一个字符串,请将字符串里的字符按照出现的频率降序排列。
pair<char,int>
,再使用STL里面的sort()函数进行排序,sort的好处是可以自定义排序的规则。 static bool cmp(pair<char, int> a, pair<char, int> b) {
return a.second > b.second;
}
string frequencySort(string s) {
unordered_map<char, int>hash;
for (auto it : s) {
hash[it]++;
}
vector<pair<char, int> > arr(hash.begin(), hash.end());
sort(arr.begin(), arr.end(), cmp);
string res;
for (auto it : arr) {
while (it.second--) {
res.push_back(it.first);
}
}
return res;
}
Leetcode给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
cur < p2
而不是cur < nums.size()
void sortColors(vector<int>& nums) {
int p0 = 0, p2 = nums.size() - 1;
int cur = 0;
while (cur < p2) {
if (nums[cur] == 1) cur++;
else if (nums[cur] == 0) swap(nums[p0++], nums[cur++]);
else if (nums[cur] == 2) swap(nums[cur],nums[p2--]);
}
}
leetcode 给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。 换而言之,对于每个 nums[i] 你必须计算出有效的 j 的数量,其中 j 满足 j != i 且 nums[j] < nums[i] 。 以数组形式返回答案。
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
int cnt[101];
memset(cnt, 0, sizeof(int) * 101);
for (int i = 0; i < nums.size(); ++i) {
cnt[nums[i]]++;
}
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
int sum = 0;
for (int j = 0 ; j < 100; ++j) {
if (nums[i] <= j) break;
sum += cnt[j];
}
res.push_back(sum);
}
return res;
}
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
int cnt[101];
memset(cnt, 0, sizeof(int) * 101);
for (int i = 0; i < nums.size(); ++i) {
cnt[nums[i]]++;
}
for (int i = 1; i < 100; ++i) {
cnt[i] += cnt[i - 1];
}
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
res.push_back(nums[i] == 0 ? 0 : cnt[nums[i] - 1]);
}
return res;
}
leetcode 给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int len = intervals.size();
int i = 0;
vector<vector<int>> res;
while (i < len && intervals[i][1] < newInterval[0]) {
res.push_back(intervals[i]);
i++;
}
while (i < len && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(intervals[i][0], newInterval[0]);
newInterval[1] = max(intervals[i][1], newInterval[1]);
i++;
}
res.push_back(newInterval);
while (i < len) {
res.push_back(intervals[i++]);
}
return res;
}
leetcode 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。 如果存在多个数字二进制中 1 的数目相同,则必须将它们按照数值大小升序排列。 请你返回排序后的数组。
vector<int> sortByBits(vector<int>& arr) {
sort(arr.begin(), arr.end(), cmp);
return arr;
}
static bool cmp(int a, int b) {
int cnta = count(a);
int cntb = count(b);
return cnta != cntb ? cnta < cntb : a < b;
}
static int count(int num) {
int cnt = 0;
while (num) {
cnt += (num % 2 == 1 ? 1 : 0);
num /= 2;
}
return cnt;
}
leetcode 给出 R 行 C 列的矩阵,其中的单元格的整数坐标为 (r, c),满足 0 <= r < R 且 0 <= c < C。 另外,我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。 返回矩阵中的所有单元格的坐标,并按到 (r0, c0) 的距离从最小到最大的顺序排,其中,两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离,|r1 - r2| + |c1 - c2|。(你可以按任何满足此条件的顺序返回答案。)
vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector<int>> matrix;
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
matrix.push_back({i, j});
}
}
sort(matrix.begin(), matrix.end(), [&](vector<int>& a, vector<int>& b){
return abs(a[0] - r0) + abs(a[1] - c0) < abs(b[0] - r0) + abs(b[1] - c0);
});
return matrix;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。