-
1122. 数组的相对排序 - 力扣（LeetCode）
法一：计数排序 O(n)
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
vector<int> temp(1001, 0);
for (int num : arr1) temp[num]++;
vector<int> ans;
for (int num : arr2)
while (temp[num]-- > 0) ans.push_back(num);
for (int i = 0; i <= 1000; i++)
while (temp[i]-- > 0) ans.push_back(i);
return ans;
}
};
法二：内置函数sort O(nlogn)
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
// <val, idx>
unordered_map<int, int> arr2Order;
for (int i = 0; i < arr2.size(); i++)
arr2Order[arr2[i]] = i;
sort(arr1.begin(), arr1.end(), [&](int x, int y) {
int xPos = arr2Order.find(x) != arr2Order.end()
? arr2Order[x] : arr2Order.size();
int yPos = arr2Order.find(y) != arr2Order.end()
? arr2Order[y] : arr2Order.size();
return xPos < yPos || (xPos == yPos && x < y);
});
return arr1;
}
};
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
});
int start = -1, farthest = -1;
vector<vector<int>> ans;
for (const vector<int>& interval : intervals) {
int left = interval[0];
int right = interval[1];
if (left <= farthest)
farthest = max(farthest, right);
else {
if (farthest != -1)
ans.push_back({start, farthest});
start = left;
farthest = right;
}
}
ans.push_back({start, farthest});
return ans;
}
};
法二：
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<pair<int, int>> events;
for (const vector<int>& interval : intervals) {
events.push_back({interval[0], 1});
events.push_back({interval[1] + 1, -1});
}
sort(events.begin(), events.end());
int covering = 0;
int start = 0;
vector<vector<int>> ans;
for (auto event : events) {
if (covering == 0) start = event.first;
covering += event.second;
if (covering == 0) ans.push_back({start, event.first - 1});
}
return ans;
}
};
-
215. 数组中的第K个最大元素 - 力扣（LeetCode）
法一：内置sort快排==O(NlogN)
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
法二：利用快排partition思想==O(N)
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return quickSort(nums, 0, nums.size() - 1, nums.size() - k);
}
private:
int quickSort(vector<int>& nums, int l, int r, int idx) {
if (l >= r) return nums[l];
int pivot = partition(nums, l, r);
if (idx <= pivot) return quickSort(nums, l, pivot, idx);
else return quickSort(nums, pivot + 1, r, idx);
}
int partition(vector<int>& nums, int l, int r) {
int pivotVal = nums[l + rand() % (r - l + 1)];
while (l <= r) {
while (nums[l] < pivotVal) l++;
while (nums[r] > pivotVal) r--;
if (l < r) {
swap(nums[l], nums[r]);
l++; r--;
}
else break;
}
return r;
}
};
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
int pos = a[n / 2];
long long ans = 0;
for (int i = 0; i < n; i++) ans += abs(pos - a[i]);
cout << ans << endl;
return 0;
}
class Solution {
public:
int reversePairs(vector<int>& nums) {
ans = 0;
mergeSort(nums, 0, nums.size() - 1);
return ans;
}
private:
int ans;
void mergeSort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
calc(nums, l, mid, r);
merge(nums, l, mid, r);
}
void merge(vector<int>& nums, int l, int mid, int r) {
int size = r - l + 1;
vector<int> temp(size);
// nums[l, mid][mid+1, r]
int i = l, j = mid + 1, k;
for (k = 0; k < size; k++)
if (j > r || (i <= mid && nums[i] <= nums[j]))
temp[k] = nums[i++];
else
temp[k] = nums[j++];
for (k = 0; k < size; k++)
nums[l + k] = temp[k];
}
void calc(vector<int>& nums, int l, int mid, int r) {
// nums[l, mid][mid+1, r]
int j = mid + 1;
for (int i = l; i <= mid; i++) {
while (j <= r && nums[i] > 2ll * nums[j]) j++;
ans += (j - mid - 1);
}
}
};
-
327. 区间和的个数 - 力扣（LeetCode）
前缀和+归并排序
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
this->lower = lower;
this->upper = upper;
long s = 0;
vector<long> sum{0};
for (auto &num : nums) {
s += num;
sum.push_back(s);
}
res = 0;
countRangeSumRecu(sum, 0, sum.size() - 1);
return res;
}
private:
int lower, upper, res;
void countRangeSumRecu(vector<long> &sum, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
countRangeSumRecu(sum, left, mid);
countRangeSumRecu(sum, mid + 1, right);
calculate(sum, left, mid, right);
merge(sum, left, mid, right);
}
void calculate(vector<long> &sum, int left, int mid, int right) {
// 此处左侧[left, mid]的原下标一定小于右侧[mid+1, right]的原下标，
// 且可以while去累加数量
// 这里可以累加，就是merge归并排序来保证的1.合并的两侧在各自原下标不相交2.有序
// 可能讲的不清楚。。。
int l = mid + 1, r = mid + 1;
for (int i = left; i <= mid; ++i) {
while (l <= right && sum[l] - sum[i] < lower)
l++;
while (r <= right && sum[r] - sum[i] <= upper)
r++;
res += (r - l);
}
}
void merge(vector<long> &sum, int left, int mid, int right) {
int size = right - left + 1;
vector<long> temp(size, 0);
int i = left, j = mid + 1, k;
for (k = 0; k < size; ++k)
if (j > right || (i <= mid && sum[i] <= sum[j]))
temp[k] = sum[i++];
else
temp[k] = sum[j++];
for (k = 0; k < size; ++k)
sum[k + left] = temp[k];
}
};
-
860. 柠檬水找零 - 力扣（LeetCode）
法一：金额有倍数关系即有决策包容性，可以贪心
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
coins[5] = coins[10] = coins[20] = 0;
for (int bill : bills) {
coins[bill]++;
if (!exchange(bill - 5)) return false;
}
return true;
}
private:
unordered_map<int, int> coins;
bool exchange(int amount) {
for (int x : {20, 10, 5})
while (amount >= x && coins[x] > 0) {
amount -= x;
coins[x]--;
}
return amount == 0;
}
};
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
// 分配给孩子满足胃口的最小饼干，具有决策包容性，可以贪心
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int ans = 0;
int j = 0;
for (int child : g) {
while (j < s.size() && s[j] < child) j++;
if (j < s.size()) {
ans++; j++;
}
}
return ans;
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
for (int i = 1; i < prices.size(); i++)
ans += max(prices[i] - prices[i - 1], 0);
return ans;
}
};
class Solution {
public:
int jump(vector<int>& nums) {
int now = 0;
int ans = 0;
while (now < nums.size() - 1) {
int right = now + nums[now];
if (right >= nums.size() - 1)
return ans + 1;
// [now+1, right]
int nextRight = right;
int next = now;
for (int i = now + 1; i <= right; i++)
// 用下下步最远的下步来确定下一步走哪
if (i + nums[i] > nextRight) {
nextRight = i + nums[i];
next = i;
}
// 如果循环后next还不变，说明从now出发怎么走都不到终点，直接退出
if (next == now) return -1;
now = next;
ans++;
}
return ans;
}
};
