当前位置:网站首页>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 :
边栏推荐
- Spend a week painstakingly sorting out the interview questions and answers of high-frequency software testing / automated testing
- Pytest testing framework
- Batch detect whether there is CDN in URL - high accuracy
- Sword finger offer 42 Maximum sum of continuous subarrays
- Comparative analysis of MVC, MVP and MVVM, source code analysis
- What are the common proxy servers and what are the differences?
- How to hide the scroll bar of scroll view in uniapp
- [liuyubobobo play with leetcode algorithm interview] [00] Course Overview
- 批量检测url是否存在cdn—高准确率
- Stack - es - official documents - filter search results
猜你喜欢
Which brand of sports headset is better? Bluetooth headset suitable for sports
MongoDB非关系型数据库
[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
Vsocde has cli every time it is opened js
Which kind of sports headphones is easier to use? The most recommended sports headphones
STM32__ 05 - PWM controlled DC motor
[learn C and fly] 2day Chapter 8 pointer (practice 8.1 password unlocking)
How to batch add background and transition effects to videos?
[staff] diacritical mark (ascending sign | descending sign B | double ascending sign x | double descending sign BB)
【带你学c带你飞】3day第2章 用C语言编写程序(练习 2.3 计算分段函数)
随机推荐
Set status bar color
Summary of some experiences in the process of R & D platform splitting
Websocket + spingboot realize code scanning login
Leetcode face T10 (1-9) array, ByteDance interview sharing
Leetcode question brushing (10) - sequential question brushing 46 to 50
C return multiple values getter setter queries the database and adds the list return value to the window
使用开源项目【Banner】实现轮播图效果(带小圆点)
[untitled]
SAP ui5 beginner tutorial 19 - SAP ui5 data types and complex data binding
Duplicate keys detected: ‘0‘. This may cause an update error. found in
Multi threaded query, double efficiency
[staff] pitch representation (treble clef | C3 60 ~ B3 71 pitch representation | C4 72 pitch representation | C5 84 pitch representation)
Opencascade7.6 compilation
研发中台拆分过程的一些心得总结
How to batch add background and transition effects to videos?
trading
实现一个自定义布局的扫码功能
连通块模板及变式(共4题)
The video number will not be allowed to be put on the shelves of "0 yuan goods" in the live broadcasting room?
2022 low voltage electrician test question simulation test question bank simulation test platform operation