当前位置:网站首页>[force buckle]41 Missing first positive number
[force buckle]41 Missing first positive number
2022-07-07 00:49:00 【wingaso】
Consistent with the topic AC Code
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while nums[i] != i + 1 and nums[i] > 0 and nums[i] < n and nums[i] != nums[nums[i] - 1]:
#nums[i],nums[nums[i] - 1] = nums[nums[i] - 1],nums[i]
t1,t2 =nums[i],nums[nums[i] - 1]
nums[nums[i] - 1] = t1
nums[i] = t2
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
Not in line with the title AC Code
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
D = {
}
for it in nums:D[it] = 1
i = 1
while i in D.keys(): i += 1
return i
analysis
Because the time complexity of this problem is O ( n ) O(n) O(n), And the value range of the element is the integer range , So the easiest way to think of is to use hash table —— With the help of hash table, mark every value that appears , The hash time of each value is O ( 1 ) O(1) O(1), The total complexity of hash is O ( n ) O(n) O(n). And then from 1 Start to find the first integer that does not appear in the hash table , The expected time complexity of the traversal process is O ( n / 2 ) O(n/2) O(n/2). So the total time complexity of this process is O ( n ) O(n) O(n), Meet the requirements of the topic . However , The problem also has strict requirements for the spatial complexity of the algorithm —— O ( 1 ) O(1) O(1) Time complexity of .
The spatial complexity of using hash tables is linear , Obviously does not meet the requirements of the topic .
For this question , Use hash table What a beautiful thing , But the space complexity of hash table is not up to standard , What are the optimization strategies ?
Here we need to use some characteristics of the data itself .
That is to build a special hash table with the help of the particularity of the data itself , achieve O ( 1 ) O(1) O(1) Complexity requirements .
As shown in the figure , We can put each number where it should be , The final result we use O ( n ) O(n) O(n) The complexity of completes the mapping of numeric values and array subscripts —— That is hash .
It should be noted that , The value of the number in the array may be negative 、 It may also be a large number .
For these numbers , We can ignore —— Because the array length is only n, So the first positive number missing cannot be greater than n + 1.
Are we using O ( n ) O(n) O(n) The time complexity of sorting an array ?
Yes .
According to conventional cognition , Sort an array , The most time complexity is O ( n l o g 2 n ) O(nlog_2n) O(nlog2n), Why can it be achieved here O ( n ) O(n) O(n) What about the order of ?
That's because we take advantage of the particularity of this array —— Or the particularity of sorting rules —— We only sort the data within a limited range of integers , And each number should not be repeated when sorting ( Otherwise, the number will be ignored ).
Topic link
Originality is not easy. , Thank you for your support !
边栏推荐
- threejs图片变形放大全屏动画js特效
- Leecode brush questions record sword finger offer 43 The number of occurrences of 1 in integers 1 to n
- 如何判断一个数组中的元素包含一个对象的所有属性值
- 学习使用代码生成美观的接口文档!!!
- Data sharing of the 835 postgraduate entrance examination of software engineering in Hainan University in 23
- Compilation of kickstart file
- Mujoco Jacobi - inverse motion - sensor
- Core knowledge of distributed cache
- Advanced learning of MySQL -- basics -- basic operation of transactions
- 三维扫描体数据的VTK体绘制程序设计
猜你喜欢
Lombok 同时使⽤ @Data 和 @Builder 的坑,你中招没?
基於GO語言實現的X.509證書
Hero League | King | cross the line of fire BGM AI score competition sharing
Idea automatically imports and deletes package settings
Telerik UI 2022 R2 SP1 Retail-Not Crack
Amazon MemoryDB for Redis 和 Amazon ElastiCache for Redis 的内存优化
equals()与hashCode()
2022/2/11 summary
37页数字乡村振兴智慧农业整体规划建设方案
Uniapp uploads and displays avatars locally, and converts avatars into Base64 format and stores them in MySQL database
随机推荐
Mujoco finite state machine and trajectory tracking
【YoloV5 6.0|6.1 部署 TensorRT到torchserve】环境搭建|模型转换|engine模型部署(详细的packet文件编写方法)
Stm32f407 ------- SPI communication
@TableId can‘t more than one in Class: “com.example.CloseContactSearcher.entity.Activity“.
. Bytecode structure of class file
PXE server configuration
Learn self 3D representation like ray tracing ego3rt
学习使用代码生成美观的接口文档!!!
509 certificat basé sur Go
Model-Free Prediction
If the college entrance examination goes well, I'm already graying out at the construction site at the moment
stm32F407-------SPI通信
MySQL learning notes (mind map)
How engineers treat open source -- the heartfelt words of an old engineer
【JokerのZYNQ7020】AXI_EMC。
Uniapp uploads and displays avatars locally, and converts avatars into Base64 format and stores them in MySQL database
浅谈测试开发怎么入门,如何提升?
Basic information of mujoco
St table
Telerik UI 2022 R2 SP1 Retail-Not Crack