Day 109, 215, ##, Kth Largest Element in an Array, Combination Sum III, Contains Duplicate

Kth Largest Element in an Array

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 [3,2,1,5,6,4] and k = 2, return 5.

Note: 
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;
    }
};

sort

class 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;
    }
};