current position：Home>leetcode 35. Search Insert Position（python）
leetcode 35. Search Insert Position（python）
20220129 16:11:47 【Wang Daya】
Little knowledge , Great challenge ！ This article is participating in “ A programmer must have a little knowledge ” Creative activities .
describe
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Copy code
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
Copy code
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
Copy code
Example 4:
Input: nums = [1,3,5,6], target = 0
Output: 0
Copy code
Example 5:
Input: nums = [1], target = 0
Output: 0
Copy code
Note:
1 <= nums.length <= 10^4
10^4 <= nums[i] <= 10^4
nums contains distinct values sorted in ascending order.
10^4 <= target <= 10^4
Copy code
analysis
According to the meaning , Gives an ordered list of integers nums And an integer target , If target stay nums in , Then directly return the index of the location , If target be not in nums in , An index guarantee is returned target Insert nums After that, it is still orderly . The idea is simple ：
 If target stay nums in , Go straight back to nums.index(target)
 Otherwise traverse nums Every element in num , If num Greater than target Directly return the index of the current location
 After traversal, if the appropriate index position is still not found , explain target Greater than nums All elements in , Go straight back to nums It's just as long as you want
The time complexity of our algorithm is required to be O(log n) , Obviously, the meaning of the question can be satisfied by directly using dichotomy , But I just don't have to , Ah, just play ～
answer
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if target in nums:
return nums.index(target)
for i, num in enumerate(nums):
if num > target:
return i
return len(nums)
Copy code
Running results
Runtime: 28 ms, faster than 96.37% of Python online submissions for Search Insert Position.
Memory Usage: 14.2 MB, less than 25.57% of Python online submissions for Search Insert Position.
Copy code
analysis
I lied to you , I'm sure I'll use the binary search method . Slightly ～
answer
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
l, r = 0, len(nums)1
while l <= r:
mid = (l + r)//2
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid + 1
else:
r = mid  1
return l
Copy code
Running results
Runtime: 38 ms, faster than 43.70% of Python online submissions for Search Insert Position.
Memory Usage: 14 MB, less than 97.13% of Python online submissions for Search Insert Position.
Copy code
Original link ：leetcode.com/problems/se…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201291611457280.html
The sidebar is recommended
 [Python introduction project] use Python to generate QR code
 Compile D + +, and use d to call C from python
 Quickly build Django blog based on function calculation
 Python collects and monitors system data  psutil
 Finally, this Python import guide has been sorted out. Look!
 Quickly build Django blog based on function calculation
 Python interface test unittest usage details
 Implementation of toplevel design pattern in Python
 You can easily get started with Excel. Python data analysis package pandas (VII): breakdown
 Python simulation random coin toss (non optimized version)
guess what you like

Python tiktok 5000+ V, and found that everyone love this video.

Using linear systems in python with scipy.linalg

Using linear systems in python with scipy.linalg

Together with Python to do a license plate automatic recognition system, fun and practical!

You can easily get started with Excel. Python data analysis package pandas (XI): segment matching

Advanced practical case: Javascript confusion of Python anti crawling

Using linear systems in python with scipy.linalg

Fast power modulus Python implementation of large numbers

Quickly build Django blog based on function calculation

This paper clarifies the chaotic switching operation and elegant derivation of Python
Random recommended
 You can easily get started with Excel pandas (I): filtering function
 You can easily get started with Excel. Python data analysis package pandas (II): advanced filtering (I)
 You can easily get started with Excel. Python data analysis package pandas (2): advanced filtering (2)
 You can easily get started with Excel. Python data analysis package pandas (3): making score bar
 Test Development: self study Dubbo + Python experience summary and sharing
 You can easily get started with Excel. Python data analysis package pandas (V): duplicate value processing
 How does Python correctly call jar package encryption to get the encrypted value?
 Python 3 interview question: give an array. If there is 0 in the array, add a 0 after 0, and the overall array length remains the same
 Python simple Snake game (single player mode)
 Using linear systems in python with scipy.linalg
 Python executes functions and even code through strings! Come and understand the operation of such a top!
 Decoding the verification code of Taobao slider with Python + selenium, the road of information security
 [Python introduction project] use Python to generate QR code
 Vanessa basks in her photos and gets caught up in the golden python. There are highlights in the accompanying text. She can't forget Kobe after all
 [windows] Python installation pyteseract
 [introduction to Python project] create bar chart animation in Python
 Fundamentals of Python I
 Python series tutorials 116
 Python code reading (chapter 35): fully (deeply) expand nested lists
 Practical series 1 ️⃣ Wechat applet automatic testing practice (with Python source code)
 Python Basics: do you know how to use lists?
 Solution of no Python 3.9 installation was detected when uninstalling Python
 [Python homework] coupling network information dissemination
 [common links of Python & Python]
 Python application software development tool  tkinterdesigner v1.0 5.1 release!
 [Python development tool tkinterdiesigner]: example: develop stock monitoring alarm using Tkinter desinger
 [Python development tool Tkinter designer]: Lecture 2: introduction to Tkinter designer's example project
 [Python development tool Tkinter designer]: Lecture 1: introduction to the basic functions of Tkinter Designer
 [introduction to Python tutorial] use Python 3 to teach you how to extract any HTML main content
 Python socket implements UDP server and client
 Python socket implements TCP server and client
 leetcode 1261. Find Elements in a Contaminated Binary Tree（python）
 [algorithm learning] 1486 Array XOR operation (Java / C / C + + / Python / go / trust)
 leetcode 1974. Minimum Time to Type Word Using Special Typewriter（python）
 The mobile phone uses Python to operate picture files
 [learning notes] Python exception handling try except...
 Two methods of using pandas to read poorly structured excel. You're welcome to take them away
 Python sum (): the summation method of Python
 Practical experience sharing: use pyo3 to build your Python module
 Using Python to realize multitasking process