current position:Home>leetcode 35. Search Insert Position(python)
leetcode 35. Search Insert Position(python)
2022-01-29 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 top-level 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