Leetcode 33 search rotation sort array 34 find the first and last position of elements in sorted array 35 search insertion position

Big sai 2020-11-13 06:03:50
leetcode search rotation sort array


Preface

The last time to punch in before National Day , Continue to open after national day , official account bigsai Reply to the group, welcome to join the punch in , If it helps, remember Like collection .

Recent punch in record :
LeetCode 32 Longest valid bracket ( difficult ) ( This week, )
LeetCode 30 Concatenate the substrings of all words &31 Next spread ( Last week, )
LeetCode 27 Remove elements &28 Realization strStr()&29 Divide two numbers ( Last week, )

I think everyone is familiar with , Binary search each time judge and compare the range of elements to compress , You can compress half the range every time , So it's too much 1 It's a size you want to see ( The worst ) Spread n Times to the original length .

 Insert picture description here

Many questions are the original dichotomy , But many questions are dichotomous variations .

33 Search rotation sort array

 Insert picture description here

This question is actually a dichotomous variant , Some other conditions have been added . Every time the mid To judge how to move . A normal sequence is divided into two sequences , And it's all incremental , There's no same .

Just take the middle mid The value is greater than target There are several situations :
 Insert picture description here
According to this way of thinking, the other half can be solved all the time .

ac The code is :

 public int search(int[] nums, int target) {

if(nums[0]==target)return 0;
if(nums[nums.length-1]==target)return nums.length-1;
int l=0;int r=nums.length-1;
while (l<r) {

int mid=(l+r)/2;
//System.out.println(mid+" "+l+" "+r);
if(nums[mid]==target)return mid;
// 8 9 2 3 4 5 6 7 
if(nums[mid]>target)// The middle is greater than the target 
{

if(nums[0]>target) {
// The far left is greater than Only in the smallest area on the right 
if(nums[mid]<nums[0])// Currently in the right area 
{

r=mid;
}
else {

l=mid+1;
}
}
else {
 The far left side is less than the target value towards the left 
r=mid;
}
}
// 8 9 2 3 4 5 6 7 
else {
// The middle is less than the target 
// If it's on the right side, to the left 
if(nums[nums.length-1]<target)// The far right side is less than target It needs to go to the left 
{

if(nums[mid]<nums[nums.length-1])// At present 
{

r=mid;
}
else {

l=mid+1;
}
}
else // The far right is greater than target In a small area 
{

l=mid+1;
}
//System.out.println(1);
}
}
return -1;
}

 Insert picture description here

34 Find the first and last positions of the elements in the sort array

 Insert picture description here
Two points for beginners , Pay attention to find a value and find the boundary problem in the left and right directions .ac The code is :

 public int[] searchRange(int[] nums, int target) {

int a[]= {
-1,-1};
if(nums.length==1&&nums[0]==target) {
a[0]=0;a[1]=0;return a;}
if(nums.length==0)return a;
int leftindex,rightindex;
int left=0,right=nums.length-1;
while (left<right) {

//System.out.println(left+" "+right);
int mid=(left+right)/2;
if(nums[mid]==target)
{

leftindex=mid;
rightindex=mid;
while (leftindex>=0&&nums[leftindex]==target) {
leftindex--;}
while (rightindex<nums.length&&nums[rightindex]==target) {
rightindex++;}
a[0]=leftindex+1;a[1]=rightindex-1;
return a;
}
else if (nums[mid]<target) {

left=mid+1;
}
else {

right=mid;
}
}
if(nums[left]==target)
{

a[0]=left;a[1]=left;
}
return a;
}

 Insert picture description here

35 Search insert location

 Insert picture description here
What we need to pay attention to is the insertion position or the number found . Classic dichotomy doesn't say much about what you know /

 public int searchInsert(int[] nums, int target) {

if(nums[0]>=target)return 0;// prune 
if(nums[nums.length-1]==target)return nums.length-1;// prune 
if(nums[nums.length-1]<target)return nums.length;
int left=0,right=nums.length-1;
while (left<right) {

int mid=(left+right)/2;
if(nums[mid]==target)
return mid;
else if (nums[mid]>target) {

right=mid;
}
else {

left=mid+1;
}
}
return left;
}

 Insert picture description here
At the end of this punch out , There will be a national day break next week ( Just once ). Welcome other brothers and sisters to punch in , WeChat search bigsai, Rejoin the group and join the clasp !
 Insert picture description here

版权声明
本文为[Big sai]所创,转载请带上原文链接,感谢

  1. [front end -- JavaScript] knowledge point (IV) -- memory leakage in the project (I)
  2. This mechanism in JS
  3. Vue 3.0 source code learning 1 --- rendering process of components
  4. Learning the realization of canvas and simple drawing
  5. gin里获取http请求过来的参数
  6. vue3的新特性
  7. Get the parameters from HTTP request in gin
  8. New features of vue3
  9. vue-cli 引入腾讯地图(最新 api,rocketmq原理面试
  10. Vue 学习笔记(3,免费Java高级工程师学习资源
  11. Vue 学习笔记(2,Java编程视频教程
  12. Vue cli introduces Tencent maps (the latest API, rocketmq)
  13. Vue learning notes (3, free Java senior engineer learning resources)
  14. Vue learning notes (2, Java programming video tutorial)
  15. 【Vue】—props属性
  16. 【Vue】—创建组件
  17. [Vue] - props attribute
  18. [Vue] - create component
  19. 浅谈vue响应式原理及发布订阅模式和观察者模式
  20. On Vue responsive principle, publish subscribe mode and observer mode
  21. 浅谈vue响应式原理及发布订阅模式和观察者模式
  22. On Vue responsive principle, publish subscribe mode and observer mode
  23. Xiaobai can understand it. It only takes 4 steps to solve the problem of Vue keep alive cache component
  24. Publish, subscribe and observer of design patterns
  25. Summary of common content added in ES6 + (II)
  26. No.8 Vue element admin learning (III) vuex learning and login method analysis
  27. Write a mini webpack project construction tool
  28. Shopping cart (front-end static page preparation)
  29. Introduction to the fluent platform
  30. Webpack5 cache
  31. The difference between drop-down box select option and datalist
  32. CSS review (III)
  33. Node.js学习笔记【七】
  34. Node.js learning notes [VII]
  35. Vue Router根据后台数据加载不同的组件(思考-&gt;实现-&gt;不止于实现)
  36. Vue router loads different components according to background data (thinking - & gt; Implementation - & gt; (more than implementation)
  37. 【JQuery框架,Java编程教程视频下载
  38. [jQuery framework, Java programming tutorial video download
  39. Vue Router根据后台数据加载不同的组件(思考-&gt;实现-&gt;不止于实现)
  40. Vue router loads different components according to background data (thinking - & gt; Implementation - & gt; (more than implementation)
  41. 【Vue,阿里P8大佬亲自教你
  42. 【Vue基础知识总结 5,字节跳动算法工程师面试经验
  43. [Vue, Ali P8 teaches you personally
  44. [Vue basic knowledge summary 5. Interview experience of byte beating Algorithm Engineer
  45. 【问题记录】- 谷歌浏览器 Html生成PDF
  46. [problem record] - PDF generated by Google browser HTML
  47. 【问题记录】- 谷歌浏览器 Html生成PDF
  48. [problem record] - PDF generated by Google browser HTML
  49. 【JavaScript】查漏补缺 —数组中reduce()方法
  50. [JavaScript] leak checking and defect filling - reduce() method in array
  51. 【重识 HTML (3),350道Java面试真题分享
  52. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  53. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  54. [re recognize HTML (3) and share 350 real Java interview questions
  55. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  56. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  57. 【重识 HTML ,nginx面试题阿里
  58. 【重识 HTML (4),ELK原来这么简单
  59. [re recognize HTML, nginx interview questions]
  60. [re recognize HTML (4). Elk is so simple