278. First wrong version
Simple difficulty 259
You are a product manager and are currently leading a team to develop new products. Unfortunately, the latest version of your product has not passed the quality test. Since each version is developed based on the previous version, all versions after the wrong version are wrong.
Suppose you have n versions [1, 2,..., n], you want to find the first wrong version that causes errors in all subsequent versions.
You can call the bool isBadVersion(version) interface to determine whether the version number is wrong in the unit test. Implement a function to find the first wrong version. You should minimize the number of calls to the API.
Example:
given n = 5，also version = 4 Is the first wrong version. call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true So, 4 is the first wrong version.
class Solution {
public:
int firstBadVersion(int n) {
if(isBadVersion(1)) return 1;
int left = 1;
int right =n;
while(right-left>1){
int mid = left+(right-left)/2;
if(isBadVersion(mid)){
right = mid;
}
else left = mid;
}
return right;
}
};
35. Search insertion position
The difficulty is simple 837
Given a sort array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, returns the position where it will be inserted in order.
You can assume that there are no duplicate elements in the array.
Example 1:
input: [1,3,5,6], 5 output: 2
Example 2:
input: [1,3,5,6], 2 output: 1
Example 3:
input: [1,3,5,6], 7 output: 4
Example 4:
input: [1,3,5,6], 0 output: 0
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(target<=nums[0])return 0;
if(target>nums[nums.size()-1]) return nums.size();
int left = 0;
int right = nums.size()-1;
while(right-left>1){
int mid = left + (right-left)/2;
if(nums[mid]>target) right = mid;
else left = mid;
}
if(nums[left]==target) return left;
else return right;
}
};
34. Find the first and last position of an element in a sorted array
Medium difficulty 655 collection sharing switch to English to receive dynamic feedback
Given an integer array nums arranged in ascending order and a target value target. Find the start and end positions of the given target value in the array.
The time complexity of your algorithm must be O(log n) level.
Returns [- 1, - 1] if the target value does not exist in the array.
Example 1:
input: nums = [5,7,7,8,8,10], target = 8 output: [3,4]
Example 2:
input: nums = [5,7,7,8,8,10], target = 6 output: [-1,-1]
int search(vector<int>& nums, int target) {
int i = 0;
int j = nums.size()-1;
while(i<=j){
int m = (i+j)/2;
if(nums[m]<=target) i = m+1;
else j = m-1;
}
int right = i;
i = 0;
j = nums.size()-1;
while(i<=j){
int m = (i+j)/2;
if(nums[m]<target) i = m+1;
else j = m-1;
}
int left = j;
return right-left-1;
}
33. Search rotation sort array
Medium difficulty 1205
The integer array nums is arranged in ascending order, and the values in the array are different from each other.
Before passing to the function, Num rotates on a previously unknown subscript k (0 < = k < num.length), making the array [num [k], Num [K + 1], nums[n-1], nums[0], nums[1], ..., Nums [k-1]] (subscript counts from 0). For example, [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2] after rotation at subscript 3.
Give you the rotated array num and an integer target. If the target value target exists in num, return its index, otherwise return - 1.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output:-1
Example 3:
Input: nums = [1], target = 0 Output:-1
Tips:
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- Each value in num is unique
- nums must rotate at some point
- -10^4 <= target <= 10^4
**Advanced: * * can you design a solution with time complexity of O(log n)?
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left<=right){
int mid = left +(right-left)/2;
if(nums[mid] == target) return mid;
if(nums[mid]<nums[left]) {//mid is on the right
if(target<nums[left]){//target is on the right
if(nums[mid]>target) right = mid -1;
else left = mid +1;
}
else{//target is on the left
right = mid -1;
}
}
else{//mid is on the left
if(target<nums[left]){//target is on the right
left = mid +1;
}
else{//target is on the left
if(nums[mid]>target) right = mid -1;
else left = mid +1;
}
}
}
return -1;
}
};
81. Search rotation sort array II
Medium difficulty 296
Suppose an array sorted in ascending order is rotated at a previously unknown point.
(for example, the array [0,0,1,2,2,5,6] may become [2,5,6,0,0,1,2]).
Write a function to determine whether a given target value exists in the array. If it exists, it returns true; otherwise, it returns false.
Example 1:
input: nums = [2,5,6,0,0,1,2], target = 0 output: true
Example 2:
input: nums = [2,5,6,0,0,1,2], target = 3 output: false
Advanced:
- This is Search rotation sort array The nums in this question may contain repeated elements.
- Does this affect the time complexity of the program? What impact will it have and why?
class Solution {
public:
bool search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left<=right){
int mid = left +(right-left)/2;
if(nums[mid]==target) return true;
if(nums[mid]==nums[left]) left++;
else if(nums[mid]<nums[left]){//mid is on the right
if(target<nums[left]){//target is on the right
if(nums[mid]>target) right = mid -1;
else left = mid +1;
}
else //target is on the left
right = mid -1;
}
else{//mid is on the left
if(target<nums[left]){//mid is on the right
left = mid +1;
}
else{
if(nums[mid]>target) right = mid -1;
else left = mid +1;
}
}
}
return false;
}
};
153. Find the minimum value in the rotation sort array
Medium difficulty 363
Suppose an array sorted in ascending order is rotated at a previously unknown point. For example, the array [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2].
Please find the smallest element.
Example 1:
Input: nums = [3,4,5,1,2] Output: 1
Example 2:
Input: nums = [4,5,6,7,0,1,2] Output: 0
Example 3:
Input: nums = [1] Output: 1
Tips:
- 1 <= nums.length <= 5000
- -5000 <= nums[i] <= 5000
- All integers in nums are unique
- Num was originally an ascending array, but it was rotated at a previously unknown point
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.size()==1)return nums[0];
int left =0;
int right = nums.size()-1;
while(right>left){
int mid = left + (right-left)/2;
if(nums[mid]<nums[right]){//mid is on the right
right = mid;
}
else
left = mid+1;
}
return nums[left];
}
};
154. Find the minimum value II in the rotation sort array
Difficulty 246
Suppose an array sorted in ascending order is rotated at a previously unknown point.
(for example, the array [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2]).
Please find the smallest element.
Note that there may be duplicate elements in the array.
Example 1:
input: [1,3,5] output: 1
Example 2:
input: [2,2,2,0,1] output: 0
explain:
- This question is Find the smallest value in the rotation sort array An extension of the topic.
- Does allowing repetition affect the time complexity of the algorithm? How and why?
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.size()==1)return nums[0];
int left =0;
int right = nums.size()-1;
while(right>left){
int mid = left + (right-left)/2;
if(nums[mid]<nums[right]){//mid is on the right
right = mid;
}
else if(nums[mid]==nums[right]){
right--;
}
else
left = mid+1;
}
return nums[left];
}
};
162. Look for peaks
Medium difficulty 386
The peak element refers to the element whose value is greater than the left and right adjacent values.
Give you an input array nums, find the peak element and return its index. The array may contain multiple peaks. In this case, just return the location of any peak.
You can assume nums[-1] = nums[n] = - ∞.
Example 1:
Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is the peak element, and your function should return its index 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: your function can return index 1, and its peak element is 2;
Or return index 5, whose peak element is 6.
Tips:
- 1 <= nums.length <= 1000
- -231 <= nums[i] <= 231 - 1
- For all valid I, there are nums [i]= nums[i + 1]
**Advanced: * * can you implement a solution with time complexity of O(logN)?
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0;
int right = nums.size()-1;
while(left<right){
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
ums[i] != nums[i + 1]`
**Advanced: * * can you implement a solution with time complexity of O(logN)?
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0;
int right = nums.size()-1;
while(left<right){
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};