current position:Home>C language algorithm problem: search insertion position
C language algorithm problem: search insertion position
2022-01-27 02:37:42 【WE-ubytt】
subject :
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 , Return to where it will be inserted in sequence .
Please use a time complexity of O(log n) The algorithm of .
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
Example 4:
Input : nums = [1,3,5,6], target = 0
Output : 0
Example 5:
Input : nums = [1], target = 0
Output : 0
Tips :
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums Arrange the array in ascending order without repeating elements
-104 <= target <= 104
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/search-insert-position
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas :
according to if Judgment condition ,left The value on the left remains less than target,right The value on the right is always greater than or equal to target, And because the end condition of the loop is left > right, therefore left In the end, it must be equal to right+1, At the end of the cycle , stay left and right Draw a vertical line between , You can just divide the array into two parts :left The left part and right On the right ,left The left part is all smaller than target, And right ending ;right All the parts on the right are greater than or equal to target, And left Led by . So the final answer must be left The location of .
Complexity analysis :
Time complexity :O(\log n)O(logn), among nn Is the length of the array . The time complexity of binary search is O(\log n)O(logn).
Spatial complexity :O(1)O(1). We just need constant space to hold a number of variables .
Code :
int searchInsert(int* nums, int numsSize, int target){
int left = 0;
int right = numsSize - 1;
while(left <= right)
{
int mid = left + (right - left) / 2;
if(target <= nums[mid])
{
right = mid - 1;
}
else{
left = mid + 1;
}
}
return left;
}
copyright notice
author[WE-ubytt],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270237409708.html
The sidebar is recommended
- Spring IOC container loading process
- [thinking] the difference between singleton mode and static method - object-oriented programming
- Hadoop environment setup (MySQL environment configuration)
- 10 minutes, using node JS creates a real-time early warning system for bad weather!
- Git tool
- Force deduction algorithm - 92 Reverse linked list II
- What is the sub problem of dynamic programming?
- C / C + +: static keyword summary
- Idea does not have the artifacts option when configuring Tomcat
- Anaconda can't open it
guess what you like
-
I don't know how to start this
-
Matlab simulation of transportation optimization algorithm based on PSO
-
MySQL slow log optimization
-
[Vue] as the window is stretched (larger, smaller, wider and higher), the text will not be displayed
-
Popular Linux distributions for embedded computing
-
Suzhou computer research
-
After installing SSL Certificate in Windows + tomcat, the domain name request is not successful. Please answer!!
-
Implementation time output and greetings of jQuery instance
-
The 72 year old uncle became popular. Wu Jing and Guo fan made his story into a film, which made countless dreamers blush
-
How to save computer research
Random recommended
- Springboot implements excel import and export, which is easy to use, and poi can be thrown away
- The final examination subjects of a class are mathematical programming, and the scores are sorted and output from high to low
- Two pronged approach, Tsinghua Professor Pro code JDK and hotspot source code notes, one-time learning to understand
- C + + recursive knapsack problem
- The use of GIT and GitHub and the latest git tutorial are easy to understand -- Video notes of crazy God speaking
- PostgreSQL statement query
- Ignition database test
- Context didn't understand why he got a high salary?, Nginxfair principle
- Bootstrap switch switch control user's guide, springcloud actual combat video
- A list that contains only strings. What other search methods can be used except sequential search
- [matlab path planning] multi ant colony algorithm grid map path planning [including GUI source code 650]
- [matlab path planning] improved genetic algorithm grid map path planning [including source code phase 525]
- Iinternet network path management system
- Appium settings app is not running after 5000ms
- Reactnative foundation - 07 (background image, status bar, statusbar)
- Reactnative foundation - 04 (custom rpx)
- If you want an embedded database (H2, hsql or Derby), please put it on the classpath
- When using stm32g070 Hal library, if you want to write to flash, you must perform an erase. If you don't let it, you can't write continuously.
- Linux checks where the software is installed and what files are installed
- SQL statement fuzzy query and time interval filtering
- 69. Sqrt (x) (c + + problem solving version with vs runnable source program)
- Fresh students are about to graduate. Do you choose Java development or big data?
- Java project: OA management system (java + SSM + bootstrap + MySQL + JSP)
- Titanic passenger survival prediction
- Vectorization of deep learning formula
- Configuration and use of private image warehouse of microservice architect docker
- Relearn JavaScript events
- For someone, delete return 1 and return 0
- How does Java dynamically obtain what type of data is passed? It is used to judge whether the data is the same, dynamic data type
- How does the database cow optimize SQL?
- [data structure] chain structure of binary tree (pre order traversal) (middle order traversal) (post order traversal) (sequence traversal)
- Webpack packaging optimization solution
- 5. Operation element
- Detailed explanation of red and black trees
- redhat7. 9 install database 19C
- Blue Bridge Cup notes: (the given elements are not repeated) complete arrangement (arrangement cannot be repeated, arrangement can be repeated)
- Detailed explanation of springboot default package scanning mechanism and @ componentscan specified scanning path
- How to solve the run-time exception of test times
- Detailed explanation of k8s management tool kubectl
- Android system view memory command