704. Dichotomous search
Given an n-element ordered (ascending) integer array nums and a target, write a function that searches for the target in nums and returns the subscript if the target exists, otherwise it returns -1.
Example 1.
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 appears in nums with subscript 4.
Example 2.
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums and therefore -1 is returned.
Tip:
You can assume that all the elements in nums are unduplicated.
n will be between [1, 10000].
Each element of nums will be between [-9999, 9999].
discrimination
Loop from beginning to end, find the return subscript, otherwise return -1 (code omitted);
Obviously, the time complexity of this algorithm is\(O(n)\),TLE hangs when the data is large QwQ;
So how do you optimize it?
Read the question again carefully and realize that there is a very important condition in the question that is not used:
given\(n\)elements are ordered!
dichotomy (positive solution)
As the name suggests, the core idea of "dichotomy" is to reduce the search scope by half each time to save time;
Because the data is ordered, the size of the data can be used as a keyword with the target\(target\)Comparative categorization;
The exact process is to take the midpoint of the interval\(mid\)together with\(target\)Comparison:
(coll.) fail (a student)\(target=mid\)Returns the subscript when
(coll.) fail (a student)\(target<mid\)When searching the left half;
(coll.) fail (a student)\(target>mid\)When searching the right half;
time complexity\(O(log_2n)\)
Note: The whole process needs to be based on array ordering!!!!
Upcode (●'◡'●)
class Solution {
public.
int search(vector<int>& nums, int target) {
int l=0,r=()-1;//l: left boundary of the interval; r: right boundary of the interval
while(l<=r){//bisection
int mid=(l+r)>>1;//find the midpoint (">>" bitwise operator sign, equivalent to /2)
if(nums[mid]==target){
return mid;
}
if(nums[mid]<target){
l=mid+1;
}
if(nums[mid]>target){
r=mid-1;
}
}
return -1; }
}
};//Ending Splash ヾ(≧▽≦*)o
35. Search for insertion locations
Given a sorted 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, return the position at which it will be inserted in order.
Please must use a time complexity of\(O(log n)\) of the algorithm.
Example 1.
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2.
Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3.
Input: nums = [1,3,5,6], target = 7
Output: 4
Tip.
\(1 <= <= 10^4\)
\(-10^4 <= nums[i] <= 10^4\)
nums is an ascending sorted array with no duplicates.
\(-10^4 <= target <= 10^4\)
Positive solution (still, dichotomous)
From the meaning of the question:
I. Target presence: two-point lookup;
Second, the target does not exist: return to the first larger than the target element subscript;
As for how to implement the second one, it is actually straightforward to find the end of the search and return the\(l\)It's fine.
Proof: a little (in fact, I do not know why QAQ messed up the miracle ah ~)
Note: the dichotomy must be based on the ordering of the data, if the question doesn't say ordered it won't work =)
Upper code (●'◡'●)
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l=0,r=()-1;
if(target<nums[0]){
return 0;
}
while(l<=r){//the equinox，no need elaborate on this
int mid=(l+r)>>1;
if(nums[mid]==target){
return mid;
}
if(nums[mid]<target){
l=mid+1;
}
if(nums[mid]>target){
r=mid-1;
}
}
return l;//Wei and Jin philosophical school amalgamating Daoist and Confucian ideals
}
};//lit. finish and scatter flowersヾ(≧▽≦*)o
\(O(log_2n)\)Running really fast ○( ^rad. no. 108＾＾)っHiahiahia....
34. Finding the first and last position of an element in a sorted array
You are given an array of integers, nums, in non-decreasing order, and a target value, target, and you are asked to find the starting and ending positions of the given target value in the array.
Returns [-1, -1] if target does not exist in the array.
You must design and implement a time complexity of\(O(log n)\) of the algorithm to solve this problem.
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]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
Tip:
\(0 <= <= 10^5\)
\(-10^9 <= nums[i] <= 10^9\)
nums is a non-decreasing array
\(-10^9 <= target <= 10^9\)
discrimination
Still loop through the array once, record the position of the last occurrence of the target after the first and then output it (code omitted);
Still, obviously, time complexity\(O(n)\)The title is a requirement.\(O(log_2n)\)The Duck qWq;
BUT!!! Arrays are ordered;
SO！！！
Positive solution (dichotomous, AGAIN)
The idea is simple, use two dichotomies to find the first occurrence and the last, respectively;
Upcode (●'◡'●)
class Solution {
public.
vector<int> searchRange(vector<int>& nums, int target) {
int l=0,r=()-1;
if(r<0){// special judgment
return vector<int>{-1,-1};
}
int lx,rx,flag=0; while(l<int>{-1,-1}; }
while(l<=r){// binary lookup first occurrence
int mid=(l+r)>>1;
if(nums[mid]==target){
r=mid-1;
r=mid-1; lx=mid; lx=mid
flag=1;
}
if(nums[mid]>target){
r=mid-1; lx=mid; flag=1; }
lx=mid; }
}
if(nums[mid]<target){
l=mid+1;
}
}
if(flag==0){ // special judgment, no such element
return vector<int>{-1,-1};
}
l=0,r=()-1;//initialization
while(l<=r){// bis lookup last occurrence
int mid=(l+r)>>1;
if(nums[mid]==target||nums[mid]<target){
l=mid+1;
rx=mid;
}
if(nums[mid]>target){
r=mid-1;
}
}
return vector<int>{lx,rx};//return answer
}
};//end scattering flowers ヾ(≧▽≦*)o
27. Removing Elements
Given an array nums and a value val, you need to remove in situ all elements whose value is equal to val. The order of the elements may change. Then return the number of elements in nums that differ from val.
Assuming that the number of elements in nums that are not equal to val is k, to pass this question you need to do the following:
Changes the nums array so that the first k elements of nums contain elements that are not equal to val. the rest of the elements of nums and the size of nums do not matter.
Returns k.
User Review:
The evaluation machine will test your solution using the following code:
int[] nums = [...] // Input array
int val = ... // The value to be removed
int[] expectedNums = [...] ; // The expected answer with the correct length. ; // The expected answers with the correct length.
// It is sorted by values not equal to val.
int k = removeElement(nums, val); // call your implementation
assert k == ;
sort(nums, 0, k); // Sort the first k elements of nums.
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
If all the assertions pass, your solution will pass.
Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, and the first two elements of nums are 2.
It doesn't matter what you leave outside of the k elements returned (so they don't count towards the rubric).
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5 and the first five elements of nums are 0,0,1,3,4.
Note that these five elements can be returned in any order.
It doesn't matter what you leave outside of the k elements returned (so they don't count towards the rubric).
Tip:
0 <= <= 100
0 <= nums[i] <= 50
0 <= val <= 100
discrimination
Every time an element is deleted, all elements after that element are moved forward;
apparent complexity\(O(n^2)\)TLE didn't run 😔;
Positive solution (fast and slow pointers + left and right double pointers)
Fast and slow pointers:
Fast pointer: find the elements of the new array , the new array is the array that does not contain the target elements
Slow pointer: points to the location where the new array subscript is updated.
Specific processes:
Code written this way:
// time complexity：O(n)
// (math.) space complexity：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < (); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};//nice
I have nothing to do with myself, and I've been working on a little optimization (the code is so ugly and unattractive QwQ):
class Solution {
public.
int removeElement(vector<int>& nums, int val) {
int k=0,n=();
if(n==0){
return 0; }
}
if(n==1){
if(n==val){
return 0; }
}
else{
return 1; } else{
}
}
int nums1[100000]={0};
if(n%2==1){// Handle the case of an odd array length
if(nums[n/2]! =val){
nums1[k]=nums[n/2];
k++;
}
}
for(int i=0,j=n-1;i<n/2;i++,j--){// Fast pointer, from both sides to the middle, halves the number of executions
if(nums[i]! =val){
nums1[k]=nums[i];
k++;// slow pointer
}
if(nums[j]! =val){
nums1[k]=nums[j];
k++;
}
}
if(n%2==1){
nums[n/2]=nums1[n/2];
}
for(int i=0,j=n-1;i<n/2;i++,j--){// Can't merge with above because it's from both sides to the center/_ \
nums[i]=nums1[i];//update
nums[j]=nums1[j];
}
return k;//return the number of elements not removed
}
};//end scattering flowers ヾ(≧▽≦*)o
complexity theory\(O(n/2)\)I'm a little ugly, but I'm a fast runner ^ O ^ Nice~
977. Squaring ordered arrays
Given an array of integers, nums, sorted in non-decreasing order, return a new array consisting of the squares of each number, also sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting the array becomes [0,1,9,16,100]
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Tip:
\(1 <= <= 10^4\)
\(-10^4 <= nums[i] <= 10^4\)
nums has been sorted in non-decreasing order.
Advancement:
Can you please design the time complexity of\(O(n\)) algorithm to solve this problem
discrimination
Iterate, square, sort;
Complexity = fast-row complexity =\(O(nlog_2n)\);
It is still possible to use double pointer optimization;
Positive solution (double pointer)
The array is ordered at the beginning, but the size of the square is determined by the absolute value
Upcode (●'◡'●)
class Solution {
public.
vector<int> sortedSquares(vector<int>& nums) {
int r=()-1,l=0,k=r;//left/right pointer and result pointer
vector<int> ans(r+1,0);//result array
while(l<=r){
if(abs(nums[l])<abs(nums[r])){//store the previous ones smaller than yourself first
ans[k] = nums[r]*nums[r];
k--;
r--;
}
else{//store yourself again
ans[k] = nums[l]*nums[l];
k--;
l++;
}
}
return ans; return result
}
};//Ending Splash ヾ(≧▽≦*)o
The time complexity is also now down to\(O(n)\)"It's a lot faster than violence!