Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given
Given
[3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
----------------------------------------------You may assume k is always valid, 1 ≤ k ≤ array's length.
quick-select。因为是in-place，注意storedIndex的初始值为left
class Solution {
public:
void swap(vector<int> &nums,int index_1, int index_2) {
int temp = nums[index_1];
nums[index_1] = nums[index_2];
nums[index_2] = temp;
}
int partition(vector<int> &nums,int left, int right) {
int mid = left + (right - left) / 2;
swap(nums,mid,right);
int storedIndex = left;
for (int i = left; i < right; i++) {
if (nums[i] <= nums[right]) {
swap(nums,i,storedIndex);
storedIndex++;
}
}
swap(nums,storedIndex,right);
return storedIndex;
}
int findKthLargest(vector<int>& nums, int k) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int pivot = partition(nums,left,right);
if (pivot == nums.size() - k) {
return nums[pivot];
}
if (pivot < nums.size() - k) {
left = pivot + 1;
}else {
right = pivot - 1;
}
}
return -1;
}
};
Combination Sum III
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
class Solution {
public:
void dfs(vector<vector<int>> &rt, vector<int> cur, int startNum, int k, int sum) {
if (k == 0 && sum == 0) {
rt.push_back(cur);
return;
}
if (k < 0 || sum < 0) return;
for (int i = startNum; i < 10; i++) {
vector<int> temp = cur;
temp.push_back(i);
dfs(rt,temp,i + 1,k - 1,sum - i);
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> rt;
vector<int> cur;
dfs(rt,cur,1,k,n);
return rt;
}
};
类似class Solution {
public:
void helper(vector<vector<int> > &rt, vector<int> cur, int target,int k, int index) {
if (k == 0 && target == 0) {
rt.push_back(cur);
return;
}
if (k < 0 || target < 0 || index > 9) return;
helper(rt,cur,target,k,index + 1);
cur.push_back(index);
helper(rt,cur,target - index,k - 1, index + 1);
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> rt;
vector<int> cur;
helper(rt,cur,n,k,1);
return rt;
}
};
Contains Duplicate Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct. ------------------------------------------------
hash set
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> st;
for (int i = 0; i < nums.size(); i++) {
if (st.find(nums[i]) != st.end()) {
return true;
}
st.insert(nums[i]);
}
return false;
}
};
sortclass Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(),nums.end());
for (int i = 1; i < nums.size(); i++) {
if (nums[i - 1] == nums[i]) {
return true;
}
}
return false;
}
};
