Search for rotation sort array II (Question number 81)

The title

An array of integers, nums, is known to exist in non-descending order, and the values in the array need not be different from each other.

Before being passed to the function, nums is rotated on some previously unknown subscript k (0 <= k < nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]] (subscript starting from 0). ,1,2,4,4,4,5,6,6,7 [0], for example, in the subscript 5 after rotation may become,5,6,6,7,0,1,2,4,4 [4].

Given your rotated array nums and an integer target, write a function to determine whether the given target value exists in the array. Return true if the target value exists in NUMs, false otherwise.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0 output: trueCopy the code

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3 output: falseCopy the code

Tip:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • Title data guaranteenumsIt’s rotated at some previously unknown index
  • -104 <= target <= 104

Advanced:

This is an extension of searching for rotated-sort arrays, where nums may contain duplicate elements. Does this affect the time complexity of the program? What’s the impact, and why?

link

Leetcode-cn.com/problems/se…

explain

This wave. This wave is the idiots.

At the beginning of the topic to see me very confused, this is not a includes? Let’s just do it. I submitted it with a shudder in case I misunderstood it. But it doesn’t. It’s really just one line of code.

But is it really that simple? It was fine after the commit, but the performance cost was in the bottom 30% range, which is not good news.

It represents the meaning is very simple, do is made, but the most stupid way.

After thinking for a while, I found that the array was originally in ascending order (containing repeated elements), but after processing, it was truncated, but the first half and the second half of the array are still in ascending order.

So all you have to do is find this break point and that break point, and take advantage of the fact that it’s all ascending, and see if the first element is greater than target, and if it is, you just go to the second part, and if it’s not, you just go to the first part.

The search method is still used includes, but the performance directly to 70%, and even sometimes the speed can be more than 90%, forced to improve a hand.

The problem is to judge where the breakpoint, the author knows that here is a dichotomy, but the situation is too much, really can not come out, wood way.

Your own way

var search = function(nums, Var mid = 0 len = nums.length start = 0 end = len - 1 for (let I = 0; i < len; I ++) {if (nums[I + 1] < nums[I]) {mid = I break}} if (target >= nums[0]) {start = 0 end = Mid + 1} else {start = mid end = len} else {start = mid end = len} mid ? nums : nums.slice(start, end) return nums.indexOf(target) > -1 };Copy the code

The comments for this code are so rich that I won’t go over them.

A Better Way (dichotomy)

The dichotomy is a little hard to do in this case, but I recommend you look at the answer to the other one. Here, it’s a little easier, there are no duplicate elements in the array, so if you understand the dichotomy in the simple case, the dichotomy in the complex case you actually have to do one more step to reevaluate the data.

So when do you redo data? When the left element, the middle element and the right element are all the same, it is impossible to judge the ascending and descending order of the subinterval, so the left element can be moved one bit to the right, and the right element can be moved one bit to the left, so as to obtain a new interval for iteration.

Code overall style that simple problem is the same, there is a more to retype conditions 👇 :

var search = function(nums, target) { var len = nums.length if (len === 1) return nums[0] === target var left = 0 right = len - 1 while (left <= Right) {var mid = ~~((left + right) / 2) if (nums[mid] === = target) return true if (nums[mid] === = nums[mid] &&  nums[mid] === nums[right]) { left++ right-- } else if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) { right = mid - 1 } else { left = mid + 1 } } else { if (nums[mid] < target && target <= nums[right]) { left = mid + 1 } else { right = mid - 1 } } } return false };Copy the code

Nothing else, just like the problem with no duplicate data.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ