在排序数组中查找数字
题目链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size() - 1;
int l = 0;
int r = n;
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
cout << r << endl;
int res = 0;
int i = l;
while(i <= n && nums[i++] == target)
res++;
return res;
}
};
搜索旋转排序数组
题目链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
if(n == 0) return -1;
int l = 0, r = n - 1;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(nums[mid] >= nums[0])
l = mid;
else
r = mid - 1;
}
if (target >= nums[0]){
// left
l = 0;
} else {
// right
l = r + 1;
r = n - 1;
}
while(l < r)
{
int mid = (l + r) >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
return nums[r] == target ? r : -1;
}
};
在排序数组中查找元素的第一个和最后一个位置
题目链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0) return {-1, -1};
vector<int> res(2, -1);
res[0] = left(nums, target);
res[1] = right(nums, target);
return res;
}
int left(vector<int>& nums, int target)
{
int n = nums.size();
int l = 0, r = n - 1;
while(l < r)
{
int mid = (l + r) >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
return target != nums[l] ? -1 : l;
}
int right(vector<int>& nums, int target)
{
int n = nums.size();
int l = 0, r = n - 1;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(nums[mid] <= target) l = mid;
else r = mid - 1;
}
return target != nums[l] ? -1 : l;
}
};
寻找两个正序数组的中位数
题目链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
归并
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> nums;
int i, j;
for(i = 0, j = 0; i < nums1.size() && j < nums2.size(); )
{
if(nums1[i] < nums2[j]) nums.push_back(nums1[i++]);
else nums.push_back(nums2[j++]);
}
while(i < nums1.size()) nums.push_back(nums1[i++]);
while(j < nums2.size()) nums.push_back(nums2[j++]);
//for_each(nums.begin(), nums.end(), [](int x) {cout << x << " ";});
cout << endl;
int n = nums.size();
if(n & 1) return nums[(n >> 1)];
else return (nums[(n >> 1) - 1] + nums[(n >> 1)]) / 2.0;
}
};
用二分求两个有序数组第k个数
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size() + nums2.size();
//两个数组长度和为奇数
if( len & 1) return getKth(nums1, nums2, (len >> 1) + 1);
//长度和为偶数
else return (getKth(nums1, nums2, len >> 1) + getKth(nums1, nums2, (len >> 1) + 1)) / 2.0;
}
int getKth(vector<int>& nums1, vector<int>& nums2, int k)
{
int n = nums1.size(), m = nums2.size();
int l = max(0, k - m), r = min(k, n);
//循环结束,l即为所求位置;
//第k小即为max(nums1[l - 1], num2(k - l - 1));
while(l < r)
{
int mid = (l + r ) >> 1;
if(nums2[k - mid - 1] > nums1[mid]) l = mid + 1;
else r = mid;
}
//由于l可以为0 和 k;
//所以l - 1和k - l - 1可能不存在,需要单独判断,防止越界
int n1_l_max = (l == 0) ? INT_MIN:nums1[l - 1];
int n2_2_max = (l == k) ? INT_MIN:nums2[k - l - 1];
return max(n1_l_max, n2_2_max);
}
};
三数之和
题目链接:https://leetcode-cn.com/problems/3sum/
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
if(nums.size() < 3) return {};
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for(int i = 0; i < nums.size() - 2; ++i)
{
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i - 1]) continue;
int target = -nums[i];
int l = i + 1, r = nums.size() - 1;
while(l < r)
{
int sum = nums[l] + nums[r];
if(sum == target)
{
res.push_back({nums[i], nums[l], nums[r]});
l++;
r--;
while(l < r && nums[l] == nums[l - 1]) l++;
while(l < r && nums[r] == nums[r + 1]) r--;
}
if(sum < target) l++;
if(sum > target) r--;
}
}
return res;
}
};