408算法题leetcode--第24天

#378. 有序矩阵中第 K 小的元素

• 378. 有序矩阵中第 K 小的元素
• 思路：值二分，如注释
• 时间：O(log(r-l) * n)；空间：O(1)

class Solution {
public:int check(vector<vector<int>>& matrix, int target){// 找<=target的个数int count = 0;int n = matrix.size();// 每一列最后一个<=target的数int i = n - 1, j = 0;while(i >= 0 && j < n){if(matrix[i][j] <= target){// 第j列有i+1个元素<=targetcount += i + 1;++j;} else {--i;}}return count;}int kthSmallest(vector<vector<int>>& matrix, int k) {// 思路1：二维 > 一维，排序，输出第k个数// 优化：值二分，计算l与mid之间的元素个数，如果<k，说明target在右段，否则在左段// 每个数的范围都在[matrix[0][0], matrix[n-1][n-1]]之间，找到第一个满足左段有k-1个数的值int n = matrix.size();int l = matrix[0][0], r = matrix[n - 1][n - 1];while(l < r){int mid = l + (r - l) / 2;if(check(matrix, mid) < k){  // <=mid的个数<kl = mid + 1;} else {r = mid;}}return l;}
};

1. 两数之和

• 1. 两数之和
• 思路1：暴力
• 思路2：哈希表；时间和空间：O(n)

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int>mp;  // val, indexint size = nums.size();for(int i = 0; i < size; i++){int complement = target - nums[i];if(mp.find(complement) != mp.end()){return {mp[complement], i};}mp[nums[i]] = i;}return {};}
};