当前位置:网站首页>Missing numbers from 0 to n-1 (simple difficulty)
Missing numbers from 0 to n-1 (simple difficulty)
2022-07-02 02:38:00 【Nulibiao】
Catalog
Title Overview ( Simple difficulty )
Ideas and code
Train of thought display
Sort the search problem in the array , think first of Dichotomy
solve .
I didn't expect this topic to use dichotomy , Let's go directly to the code , It seems that I have done less
Code example
class Solution {
public int missingNumber(int[] nums) {
int i =0,j = nums.length - 1;
while(i <= j) {
int mid = (i+j)/2;
if(nums[mid] == mid) {
i= mid+1;
}else {
j = mid-1;
}
}
return i;
}
}
matters needing attention
1: Let's first look at the core idea
if(nums[mid] == mid) {
i= mid+1;
}else {
j = mid-1;
}
Because we have a length of n-1 Incremental sort array of , And every number is in the range 0~n-1 within , The meaning of this sentence is equivalent to that the value of the array subscript is equal to the value stored in the array , for example :nums[0]=0,nums[1]=1…
So when nums[mid] = mid When , It means that the numbers leading up to the subscript in our middle are the same as those of its subscript , Without us nums[mid] It can't be equal to mid Of , Then the missing numbers in our array can only be found in our mid After subscript , So we can discard half of the data every time , Every time it goes down 1/2 The scale of , Similar to a binary tree , The number of searches is the height of the binary tree , Therefore, the complexity is reduced to log2N --> O(logN)
. So let i=mid+1, contrary , If nums[mid] != mid, Explain that the number that is less can only be in our mid Before subscribing , At this point, we need j = mid-1
2:
Now our while In circulation i Yes, we must Less than or equal to j
Of :
If it's less than j Words , At this time, the following test cases will fail :
边栏推荐
- Systemserver service and servicemanager service analysis
- AcWing 245. Can you answer these questions (line segment tree)
- The video number will not be allowed to be put on the shelves of "0 yuan goods" in the live broadcasting room?
- 附加:信息脱敏;
- Soul app released the annual report on generation Z behavior: nearly 20% of young people love shopping in the vegetable market
- The middle element and the rightmost element of the shutter
- JVM面试篇
- Is bone conduction earphone better than traditional earphones? The sound production principle of bone conduction earphones is popular science
- Types of exhibition items available in the multimedia interactive exhibition hall
- STM32F103——两路PWM控制电机
猜你喜欢
[staff] pitch representation (treble clef | C3 60 ~ B3 71 pitch representation | C4 72 pitch representation | C5 84 pitch representation)
Jvm-01 (phased learning)
批量检测url是否存在cdn—高准确率
【读书笔记】程序员修炼手册—实战式学习最有效(项目驱动)
【带你学c带你飞】3day第2章 用C语言编写程序(练习 2.3 计算分段函数)
【OpenCV】-5种图像滤波的综合示例
Software development life cycle -- waterfall model
Summary of some experiences in the process of R & D platform splitting
Analysis of FLV packaging format
CoordinatorLayout + TabLayout + ViewPager2(里面再嵌套一个RecyclerView),RecyclerView的滑动冲突解决
随机推荐
超图iServer rest服务之feature查询
[untitled]
软件开发生命周期 --瀑布模型
Coordinatorlayout + tablayout + viewpager2 (there is another recyclerview nested inside), and the sliding conflict of recyclerview is solved
Which brand of running headphones is good? How many professional running headphones are recommended
2022 safety officer-c certificate examination questions and mock examination
Systemserver service and servicemanager service analysis
[staff] the direction of the symbol stem and the connecting line (the symbol stem faces | the symbol stem below the third line faces upward | the symbol stem above the third line faces downward | the
C return multiple values getter setter queries the database and adds the list return value to the window
QT实现界面跳转
Face++ realizes face detection in the way of flow
Software development life cycle -- waterfall model
使用开源项目【Banner】实现轮播图效果(带小圆点)
Sword finger offer II 031 Least recently used cache
【OpenCV】-5种图像滤波的综合示例
What is the function of the headphone driver
【读书笔记】程序员修炼手册—实战式学习最有效(项目驱动)
Questions d'entrevue
Cesium dynamic diffusion point effect
[learn C and fly] 2day Chapter 8 pointer (practice 8.1 password unlocking)