二分专题
704. 二分查找
给定一个 n 个元素有序的（升序）整型数组
nums 和一个目标值 target ，写一个函数搜索
nums 中的
target，如果目标值存在返回下标，否则返回
-1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
Code
240301
class Solution {
public:
int search(vector<int>& nums, int target) {
auto it=lower_bound(nums.begin(),nums.end(),target);
if(it!=nums.end() && *it==target){
int len=it-nums.begin();
return len;
}else return -1;
}
};35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
Code
240301
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
auto it=lower_bound(nums.begin(),nums.end(),target);
int len=it-nums.begin();
return len;
}
};744. 寻找比目标字母大的最小字母
给你一个字符数组
letters，该数组按非递减顺序排序，以及一个字符
target。letters
里至少有两个不同的字符。
返回 letters 中大于 target
的最小的字符。如果不存在这样的字符，则返回 letters
的第一个字符。
示例 1：
输入: letters = ["c", "f", "j"]，target = "a"
输出: "c"
解释：letters 中字典上比 'a' 大的最小字符是 'c'。示例 2:
输入: letters = ["c","f","j"], target = "c"
输出: "f"
解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'。示例 3:
输入: letters = ["x","x","y","y"], target = "z"
输出: "x"
解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。提示：
2 <= letters.length <= 104letters[i]是一个小写字母letters按非递减顺序排序letters最少包含两个不同的字母target是一个小写字母
Code
240301
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
auto it=upper_bound(letters.begin(),letters.end(),target);
if(it!=letters.end()) return *it;
else return letters.front();
}
};33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值
互不相同 。
在传递给函数之前，nums 在预先未知的某个下标
k（0 <= k < nums.length）上进行了
旋转，使数组变为
[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标
从 0 开始 计数）。例如， [0,1,2,4,5,6,7]
在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]
。
给你 旋转后 的数组 nums 和一个整数
target ，如果 nums 中存在这个目标值
target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1示例 3：
输入：nums = [1], target = 0
输出：-1提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
Code
240301
class Solution {
public:
vector<int> num;
int tar;
int left(int begin,int end){
if(begin>end) return -1;
int mid=(begin+end)/2;
if(num[mid]==tar) return mid;
if(num[mid]>tar) return left(begin,mid-1);
if(num[mid]<num[0]) return left(begin,mid-1);
return left(mid+1,end);
}
int right(int begin,int end){
if(begin>end) return -1;
int mid=(begin+end)/2;
if(num[mid]==tar) return mid;
if(num[mid]<tar) return right(mid+1,end);
if(num[mid]>num.back()) return right(mid+1,end);
return right(begin,mid-1);
}
int search(vector<int>& nums, int target) {
num=nums;
tar=target;
int n=nums.size();
if(nums.back()<target) return left(0,n-1);
else return right(0,n-1);
}
};153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由
1 到 n 次 旋转
后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7]
在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组
[a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums
，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的
最小元素 。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
Code
240301
class Solution {
public:
vector<int> num;
int find(int begin,int end){
if(begin==end) return begin;
int mid=(begin+end)/2;
if(num[mid]>num.back()) return find(mid+1,end);
// if(num[mid]<num.front())
return find(begin,mid);
}
int findMin(vector<int>& nums) {
if(nums.front()<nums.back()) return nums.front();
num=nums;
return nums[find(0,nums.size()-1)];
}
};154. 寻找旋转排序数组中的最小值 II
已知一个长度为 n 的数组，预先按照升序排列，经由
1 到 n 次 旋转
后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7]
在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,4] - 若旋转
7次，则可以得到[0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组
[a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums
，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的
最小元素 。
你必须尽可能减少整个过程的操作步骤。
示例 1：
输入：nums = [1,3,5]
输出：1示例 2：
输入：nums = [2,2,2,0,1]
输出：0提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums原来是一个升序排序的数组，并进行了1至n次旋转
进阶：这道题与 寻找旋转排序数组中的最小值
类似，但 nums
可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
Code1
240301
class Solution {
public:
int find(vector<int>& nums,int begin,int end){
cout<<"begin="<<begin<<",end="<<end<<endl;
if(begin>end) return -1;
if(begin==end) return begin;
int mid=(begin+end)/2;
cout<<"mid="<<mid<<endl;
if(nums[mid]>nums.front()) return find(nums,mid+1,end);
else if(nums[mid]<nums.front()) return find(nums,begin,mid);
else{
cout<<"##"<<endl;
int temp1=find(nums,begin,mid-1);
int temp2=find(nums,mid+1,end);
cout<<"temp1="<<temp1<<",temp2="<<temp2<<endl;
if(temp1==-1 && temp2==-1) return -1;
if(temp1==-1) return temp2;
if(temp2==-1) return temp1;
return (nums[temp1]<nums[temp2])?temp1:temp2;
// if(temp1!=-1) return temp1;
// else return temp2;
}
}
int findMin(vector<int>& nums) {
if(nums.front()<nums.back()) return nums.front();
int begin=0,end=nums.size()-1;
if(nums.front()>nums.back()){
while(begin<end){
int mid=(begin+end)/2;
if(nums[mid]>=nums.front()){
begin=mid+1;
}else if(nums[mid]<=nums.back()){
end=mid;
}
cout<<"begin="<<begin<<",end="<<end<<endl;
}
}else{
begin=find(nums,begin,end);
}
return nums[begin];
}
};Code2
240302
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.front()<nums.back()) return nums.front();
int begin=0,end=nums.size()-1;
while(begin<end){
int mid=(begin+end)/2;
if(nums[mid]<nums[end]){
end=mid;
}else if(nums[mid]>nums[end]){
begin=mid+1;
}else{
end--;
}
}
return nums[begin];
}
};74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target
在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
Code
240302
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int begin=0,end=matrix.size()-1;
while(begin<end){
cout<<"begin="<<begin<<",end="<<end<<endl;
int mid=(begin+end+1)/2;
if(matrix[mid][0]>target) end=mid-1;
else if(matrix[mid][0]<=target) begin=mid;
}
int row=begin;
cout<<"row="<<row<<endl;
begin=0,end=matrix[row].size()-1;
while(begin<end){
cout<<"begin="<<begin<<",end="<<end<<endl;
int mid=(begin+end+1)/2;
if(matrix[row][mid]>target) end=mid-1;
else if(matrix[row][mid]<=target) begin=mid;
}
return target==matrix[row][begin];
}
};代码
测试用例
测试用例
测试结果
已解答
中等
相关标签
相关企业
提示
给你一个整数数组 citations ，其中
citations[i] 表示研究者的第 i
篇论文被引用的次数，citations 已经按照
升序排列 。计算并返回该研究者的 h 指数。
h
指数的定义：h 代表“高引用次数”（high citations），一名科研人员的
h 指数是指他（她）的 （n
篇论文中）至少 有 h
篇论文分别被引用了至少 h 次。
请你设计并实现对数时间复杂度的算法解决此问题。
示例 1：
输入：citations = [0,1,3,5,6]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有3篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。示例 2：
输入：citations = [1,2,100]
输出：2提示：
n == citations.length1 <= n <= 1050 <= citations[i] <= 1000citations按 升序排列
Code
240302
class Solution {
public:
int hIndex(vector<int>& citations) {
int n=citations.size();
// if(n==1 && citations[0]==0) return 0;
int begin=0,end=n-1;
while(begin<end){
cout<<"begin="<<begin<<",end="<<end<<endl;
int mid=begin+(end-begin)/2;
if(citations[mid]>=n-mid) end=mid;
else begin=mid+1;
}
if(n-begin<=citations[begin]) return n-begin;
return 0;
}
};540. 有序数组中的单一元素
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和
O(1) 空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2示例 2:
输入: nums = [3,3,7,7,10,11,11]
输出: 10提示:
1 <= nums.length <= 1050 <= nums[i] <= 105
Code
230302
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int n=nums.size();
int begin=0,end=n-1;
while(begin<end){
cout<<begin<<" "<<end<<endl;
int mid=begin+(end-begin)/2;
if(nums[mid+1]==nums[mid]){
if(mid%2==0) begin=mid+2;
else end=mid-1;
}else if(nums[mid-1]==nums[mid]){
if((mid-1)%2==0) begin=mid+1;
else end=mid-2;
}else begin=end=mid;
}
return nums[begin];
}
};852. 山脉数组的峰顶索引
符合下列属性的数组 arr 称为 山脉数组
：
arr.length >= 3存在
i（
0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回满足
arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
的下标 i 。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
示例 1：
输入：arr = [0,1,0]
输出：1示例 2：
输入：arr = [0,2,1,0]
输出：1示例 3：
输入：arr = [0,10,5,2]
输出：1提示：
3 <= arr.length <= 1050 <= arr[i] <= 106- 题目数据保证
arr是一个山脉数组
Code
240302
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n=arr.size();
int begin=0,end=n-1;
while(begin<end){
int mid=(begin+end)/2;
if(arr[mid]>arr[mid+1] && arr[mid]>arr[mid-1]) begin=end=mid;
else if(arr[mid]>arr[mid+1]) end=mid;
else begin=mid;
}
return begin;
}
};658. 找到 K 个最接近的元素
给定一个 排序好 的数组 arr ，两个整数
k 和 x ，从数组中找到最靠近
x（两数之差最小）的 k
个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x
需要满足：
|a - x| < |b - x|或者|a - x| == |b - x|且a < b
示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]提示：
1 <= k <= arr.length1 <= arr.length <= 104arr按 升序 排列-104 <= arr[i], x <= 104
Code
230302
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int n=arr.size();
int begin=0,end=n-1;
while(begin<end){
int mid=(begin+end)/2;
if(arr[mid]==x) begin=end=mid;
else if(arr[mid]<x) begin=mid+1;
else end=mid;
}
vector<int> v;
int left=begin-1,right=begin;
while(k && right<n && left>=0){
if(x-arr[left]>arr[right]-x) v.push_back(arr[right++]);
else v.push_back(arr[left--]);
k--;
}
while(k && left>=0){
v.push_back(arr[left--]);
k--;
}
while(k && right<n){
v.push_back(arr[right++]);
k--;
}
sort(v.begin(),v.end());
return v;
}
};611. 有效三角形的个数
给定一个包含非负整数的数组 nums
，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3示例 2:
输入: nums = [4,2,3,4]
输出: 4提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
Code
230302
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
int sum=0;
for(auto i=nums.begin();i<nums.end();i++){
for(auto j=i+1;j<nums.end();j++){
auto it_begin=upper_bound(i+1,j,*j-*i);
sum+=j-it_begin;
}
}
return sum;
}
};2300. 咒语和药水的成功对数
给你两个正整数数组 spells 和 potions
，长度分别为 n 和 m ，其中
spells[i] 表示第 i
个咒语的能量强度，potions[j] 表示第 j
瓶药水的能量强度。
同时给你一个整数 success 。一个咒语和药水的能量强度
相乘 如果 大于等于
success ，那么它们视为一对 成功
的组合。
请你返回一个长度为 n 的整数数组 pairs，其中
pairs[i] 是能跟第 i 个咒语成功组合的
药水 数目。
示例 1：
输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。示例 2：
输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。提示：
n == spells.lengthm == potions.length1 <= n, m <= 1051 <= spells[i], potions[i] <= 1051 <= success <= 1010
Code
240302
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success){
int n=spells.size();
int m=potions.size();
sort(potions.begin(),potions.end());
vector<int> v(n);
for(int i=0;i<n;i++){
int begin=0,end=m-1;
while(begin<end){
int mid=begin+(end-begin)/2;
if((long long)spells[i]*potions[mid]<success) begin=mid+1;
else end=mid;
}
if((long long)spells[i]*potions[begin]<success) v[i]=0;
else v[i]=m-begin;
}
return v;
}
};1498. 满足条件的子序列数目
已解答
中等
相关标签
相关企业
提示
给你一个整数数组 nums 和一个整数 target
。
请你统计并返回 nums 中能满足其最小元素与最大元素的
和 小于或等于 target 的
非空 子序列的数目。
由于答案可能很大，请将结果对 109 + 7 取余后返回。
示例 1：
输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)示例 2：
输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]示例 3：
输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）提示：
1 <= nums.length <= 1051 <= nums[i] <= 1061 <= target <= 106
Code
230303
class Solution {
public:
const int MOD=1000000007;
// 快速幂
// unordered_map<int,int> ump;
// int fastPow(int exp){
// int result=1;
// int base=2;
// while(exp>0){
// if (exp & 1) result = (long long)result * base % MOD;
// base = (long long)base * base % MOD;
// exp >>= 1;
// }
// return result;
// }
int numSubseq(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<int> powers(nums.size(),1);
for(int i=1;i<nums.size();i++){
powers[i]=(powers[i-1]*2)%MOD;
}
int sum=0;
for(auto i=nums.begin();i!=nums.end();i++){
if(target<=*i) break;
auto it=upper_bound(nums.begin(),i,target-*i);
// int len=min(it-nums.begin(),i-nums.begin());
sum=(sum+powers[i-nums.begin()]-powers[i-it])%MOD;
// for(auto j=nums.begin();j<min(it,i);j++){
// sum=(sum+powers[i-j-1])%MOD;
// // 快速幂
// // if(!ump[i-j-1]) ump[i-j-1]=fastPow(i-j-1);
// // sum=(sum+ump[i-j-1])%MOD;
// }
if(*i*2<=target) sum++;
// Old Version(WA)
// it--;
// cout<<endl;
// cout<<i-nums.begin()<<endl;
// if(*i*2>target) while(it>=nums.begin()){
// sum=(sum+(int)pow(2,i-it)-1)%1000000007;
// cout<<(int)pow(2,i-it)-1<<endl;
// it--;
// }else while(it>=nums.begin()){
// sum=(sum+(int)pow(2,i-it))%1000000007;
// cout<<(int)pow(2,i-it)<<endl;
// it--;
// }
}
if(sum<0)sum+=MOD;
return sum%MOD;
}
};34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值
target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回
[-1, -1]。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]示例 3：
输入：nums = [], target = 0
输出：[-1,-1]提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
Code1
240324
传统写法
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n=nums.size();
if(n==0) return vector<int>{-1,-1};
int res_l,res_r;
int left=0,right=n-1;
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]<target) left=mid+1;
else right=mid;
}
if(nums[left]==target) res_l=left;
else return vector<int>{-1,-1};
left=0,right=n-1;
while(left<right){
int mid=left+(right-left+1)/2;
if(nums[mid]>target) right=mid-1;
else left=mid;
}
res_r=left;
return vector<int>{res_l,res_r};
}
};Code2
240324
用了STL
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size()==0) return vector<int>{-1,-1};
int res_l,res_r;
auto it=lower_bound(nums.begin(),nums.end(),target);
if(it==nums.end() || *it!=target) return vector<int>{-1,-1};
res_l=it-nums.begin();
it=upper_bound(it,nums.end(),target);
res_r=it-nums.begin()-1;
return vector<int>{res_l,res_r};
}
};69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的
算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。提示：
0 <= x <= 231 - 1
Code
240324
class Solution {
public:
int mySqrt(int x) {
long long left=0,right=x;
while(left<right){
long long mid=left+(right-left+1)/2;
if(mid*mid>x) right=mid-1;
else left=mid;
}
return (int)left;
}
};81. 搜索旋转排序数组 II
已知存在一个按非降序排列的整数数组 nums
，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标
k（0 <= k < nums.length）上进行了
旋转 ，使数组变为
[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标
从 0 开始 计数）。例如，
[0,1,2,4,4,4,5,6,6,7] 在下标 5
处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4]。
给你 旋转后 的数组 nums 和一个整数
target
，请你编写一个函数来判断给定的目标值是否存在于数组中。如果
nums 中存在这个目标值 target ，则返回
true ，否则返回 false 。
你必须尽可能减少整个操作步骤。
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
进阶：
- 这是 搜索旋转排序数组
的延伸题目，本题中的
nums可能包含重复元素。 - 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
Code
240324
class Solution {
public:
bool search(vector<int>& nums, int target) {
if(nums.size()==0) return false;
if(nums.size()==1) return nums.front()==target;
if(nums.front()==target) return true;
if(nums.front()==nums.back()){
while(nums.size() && nums.back()==nums.front()) nums.pop_back();
if(!nums.size()) return false;
}
// if(nums.back()==target) return true;
int left=0,right=nums.size()-1;
if(target>=nums[left])
while(left<=right){
cout<<"1:"<<left<<","<<right<<"\n";
int mid=(left+right)/2;
if(nums[mid]==target) return true;
else if(nums[mid]<nums.front()) right=mid-1;
else if(nums[mid]>target) right=mid-1;
else left=mid+1;
}else while(left<=right){
cout<<"2:"<<left<<","<<right<<"\n";
int mid=left+(right-left)/2;
if(nums[mid]==target) return true;
else if(nums[mid]>nums.back()) left=mid+1;
else if(nums[mid]<target) left=mid+1;
else right=mid-1;
}
return false;
}
};162. 寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组
nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回
任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。提示：
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
Code1
240324
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int Max=INT_MIN,Max_index=0;
for(int i=0;i<nums.size();i++){
if(nums[i]>Max){
Max=nums[i];
Max_index=i;
}
}
return Max_index;
}
};Code2
240324
这个二分的速度居然没有直接遍历快
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n=nums.size();
if(n==1) return 0;
if(n==2) return (nums[0]>nums[1])?0:1;
int left=0,right=n-1;
while(left<=right){
int mid=(left+right)/2;
cout<<left<<","<<right<<"\n";
if(mid==0){
if(nums[0]>nums[1]) return 0;
else left++;
}else if(mid==n-1){
if(nums[n-1]>nums[n-2]) return n-1;
else right--;
}else{
if(nums[mid-1]>nums[mid] && nums[mid]>nums[mid+1]) right=mid-1;
else if(nums[mid-1]<nums[mid] && nums[mid]>nums[mid+1]) return mid;
else if(nums[mid-1]<nums[mid] && nums[mid]<nums[mid+1]) left=mid+1;
else left=mid+1;
}
}
return -1;
}
};167. 两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers
，该数组已按 非递减顺序排列
，请你从数组中找出满足相加之和等于目标数 target
的两个数。如果设这两个数分别是 numbers[index1] 和
numbers[index2]，则
1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2]
的形式返回这两个整数的下标 index1 和
index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers按 非递减顺序 排列-1000 <= target <= 1000- 仅存在一个有效答案
Code
240324
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n=numbers.size();
for(int i=0;i<n;i++){
auto it=upper_bound(numbers.begin(),numbers.end(),target-numbers[i])-1;
if(*it+numbers[i]==target && it-numbers.begin()!=i) return vector<int>{i+1,(int)(it-numbers.begin())+1};
}
return vector<int>{-1,-1};
}
};209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数
target 。
找出该数组中满足其总和大于等于 target 的长度最小的
连续
子数组
[numsl, numsl+1, ..., numsr-1, numsr]
，并返回其长度。如果不存在符合条件的子数组，返回
0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。示例 2：
输入：target = 4, nums = [1,4,4]
输出：1示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。
Code
240324
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n=nums.size();
vector<int> prefix_sum(n+1);
for(int i=1;i<=n;i++){
prefix_sum[i]=prefix_sum[i-1]+nums[i-1];
}
long minLen=INT_MAX;
for(int i=0;i<=n;i++){
auto it=lower_bound(prefix_sum.begin(),prefix_sum.end(),target+prefix_sum[i]);
if(it!=prefix_sum.end()){
minLen=min(minLen,it-prefix_sum.begin()-i);
}
}
return (minLen==INT_MAX)?0:minLen;
}
};class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n=nums.size();
for(int i=1;i<n;i++){
nums[i]+=nums[i-1];
}
auto it=lower_bound(nums.begin(),nums.end(),target);
if(it==nums.end()) return 0;
long minLen=it-nums.begin()+1;
for(int i=0;i<n;i++){
it=lower_bound(nums.begin()+i,nums.end(),target+nums[i]);
if(it==nums.end()) break;
minLen=min(minLen,it-nums.begin()-i);
}
return minLen;
}
};222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root
，求出该树的节点个数。
完全二叉树
的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第
h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6示例 2：
输入：root = []
输出：0示例 3：
输入：root = [1]
输出：1提示：
- 树中节点的数目范围是
[0, 5 * 104] 0 <= Node.val <= 5 * 104- 题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为
O(n) 的简单解决方案。你可以设计一个更快的算法吗？
Code
240325
class Solution {
public:
int countNodes(TreeNode* root) {
if(root==NULL) return 0;
int depth=1;
TreeNode* cur=root;
while(cur->left){
cur=cur->left;
depth++;
}
// cout<<depth<<"\n";
int left=1<<(depth-1),right=(1<<depth)-1;
while(left<right){
// cout<<"\n"<<left<<","<<right<<"\n\n";
int mid=(left+right+1)/2;
cur=root;
for(int i=2;i<depth;i++){
// cout<<depth-i<<","<<((mid>>(depth-i))&1)<<"\n";
if((mid>>(depth-i))&1){
cur=cur->right;
}else{
cur=cur->left;
}
}
if((mid&1)==1 && cur->right) left=mid;
else if((mid&1)==0 && cur->left) left=mid;
else right=mid-1;
}
return left;
}
};34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值
target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回
[-1, -1]。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]示例 3：
输入：nums = [], target = 0
输出：[-1,-1]提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
Code
240716
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res={-1,-1};
int size=nums.size();
if(size==0) return res;
if(size==1){
if(nums[0]==target){
return {0,0};
}else{
return res;
}
}
int l=0,r=size-1,m;
while(l<r){
m=(l+r+1)>>1;
if(nums[m]>=target) r=m-1;
else l=m;
}
if(nums[l]==target) res[0]=l;
else if(l+1<size && nums[l+1]==target) res[0]=l+1;
else return res;
l=0,r=size-1;
while(l<r){
m=(l+r)>>1;
if(nums[m]<=target) l=m+1;
else r=m;
}
if(nums[l]==target) res[1]=l;
else res[1]=l-1;
return res;
}
};二分专题
https://acm.nanyan.cc/posts/e3e8.html