Algorithms practice:leetcode 33. Search in Rotated Sorted Array

这篇具有很好参考价值的文章主要介绍了Algorithms practice:leetcode 33. Search in Rotated Sorted Array。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Algorithms practice:leetcode33 Search in Rotated Sorted Array

Description

There is an integer array ,nums, sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated,at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated, at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums, after the possible rotation ,and an integer target, we need to return ,the index of the target ,if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints

Constraints:

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104

code

class Solution {
public:
    int search(vector<int>& nums, int target) {//O(N) O(log(n))
        int left =0;    
        int right = nums.size()-1;  

        while(left<=right)
        {
            int mid = (left+right)/2; 
             if (nums[mid] == target) 
            {
                return mid;
            }
            
            if(nums[left] <=nums[mid]) // [left , mid] order subarray
            {
                if(nums[left] <=target && target< nums[mid])
                {
                    right = mid-1;
                }
                else//( target> nums[mid] || target< nums[right])
                {
                    left = mid+1;
                }

            }
            else
            {
                // [mid , right] order subarray
                if(nums[mid] <target && target<= nums[right])
                {
                    left = mid+1;
                }
                else //( target> nums[mid] || target< nums[right])
                {
                     right = mid-1;
                }

            }
        }
        return -1;
    }
};

讲稿

today we talk about leetcode33 Search in Rotated Sorted Array.
here is a problem.

读完题之后

The first time I was reading the question, to be honest, I didn’t understand the question. Because it is confusing, and it’s not your fault to not understand this question. Why we are getting this confusing question in interview? Why interviewer trying to give a hard time? Interview is mock working senario, and we are getting confuse and complex requirement all the time, we should be capable of getting the useful information from the complex conditions and able to solve the problem with code.

So let’s take a look together, and to find out which part it’s confusing, and what the question is really asking for.

For this question,The keyword is “rotate”, and it tells us how to rotate with the formula. we need to know what’s pivot k, index and array.

So let’s try an example with numbers.

the original array is [10,11,12,13,14,15,16,17]
look at this picture: the vertical axis represents elements in array while the horizontal axis represents indexs of the elements.
Algorithms practice:leetcode 33. Search in Rotated Sorted Array,程序员英语面试,leetcode,算法

Suppose the pivot index is 3, We cut the array at pivot 3, move the left part to the end of the array. then, we get rotated array at pivot index 3 :
[13,14,15,16,17, 10,11,12]

here I list all rotated arrays with pivot from 0 to 7.

If the pivot index is zero then the array Doesn’t change/Remains the same.

If the pivot is 1 then the rotated array looks like this.
If the pivot is 2 then the rotated array looks like this.
If the pivot is 3 then the rotated array looks like this.
If the pivot is 4 then the rotated array looks like this.
If the pivot is 5 then the rotated array looks like this.
If the pivot is 6 then the rotated array looks like this.
If the pivot is 7 then the rotated array looks like this.

the next step is to think about what algorithm we want to use to solve the problem. My first thought is to search the pivot linerly, and the time complexity is O(n), but it failed to fulfill the requirment. And time complexity of binary search is O(logn), so I want to try binary search next.

Let’s try an example with numbers.

The main idea is to divide the search space into two halves from the middle . If the middle element is the target, the process terminates. If not, we decide which subarray to continue the search in (If not, we decide in which sub-array to continue the search.). The key to the problem is how to choose the subarray.

Now please take a closer look at this picture now I’m going to split the rotated array in half.
we can see the pivot index k = 2 and nums is [12,13,14,15,16,17, 10,11]
, and the target is 13, Now let’s try to split this rotated array in half from the middle.

Algorithms practice:leetcode 33. Search in Rotated Sorted Array,程序员英语面试,leetcode,算法
we select index 3 as the middle element.
The sub-array on the left is [12 13 14 15], and the sub-array on the right is [16 17 10 11].

The left sub-array is in ascending order, and first we determine if the target is in this array.

if target >= nums[left] and target =< nums[middle]

if the target is larger than or equals nums[left] and smaller than or equals nums[middle], then we know the target can be found in this subarray.

In this case, our target is 13, which satisfies the conditions 12<13 and 13<15. Therefore, the target must be in this sub-array. So, we use this sub-array in the next iteration. Sometimes the target is not in the left subarray. in that case, we use the right sub-array in the next iteration. We will talk about what to do in that case later.

now we write the code:
firstly, we declare two int variables as Pointers: a left pointer and a right pointer and assign 0 to the left pointer ,assign nums.size()-1 to the right pointer .

int left =0;
int right = nums.size()-1;

we use while loop. In each iteration , we first need to calculate the middle pointer as (left +right )/2 (divided by 2). If the middle element is the target, we return the index of the middle element. if not, we search the target in the subarray in asending order. how do we determine which one that is?

 while(left<=right)
 {
     int mid = (left+right)/2; 
      if (nums[mid] == target) 
     {
         return mid;
     }
     
    ....
     }
 }

we first check the left one.
if nums[left] <=nums[mid], then we know the elements in the left subarray are in asending order.

the next step is to check if the target is in it. If it is,We are gonna use the left subarray in the next iteration.
that means we no longer need the right subarray, we can get rid of it by assign mid -1 to the right pointer.

 if(nums[left] <=nums[mid]) // [left , mid] order subarray
 {
      if(nums[left] <=target && target< nums[mid])
      {
          right = mid-1;
      }
      else//( target> nums[mid] || target< nums[right])
      {
          left = mid+1;
      }

  }

if the target is not in the left subarray, Then it must be in the right one. that means we don’t need the left subway. so how do we get rid of it? (问)
we can get rid of it by assign mid+1 to the right pointer.
Algorithms practice:leetcode 33. Search in Rotated Sorted Array,程序员英语面试,leetcode,算法
In the scenario we just discussed, the left subarray is in Ascending order, Now let’s talk about what to do if the right sub array is in Ascending order.

else
  {
      // [mid , right] order subarray
      if(nums[mid] <target && target<= nums[right])
      {
          left = mid+1;
      }
      else //( target> nums[mid] || target< nums[right])
      {
           right = mid-1;
      }

the next step is to check if the target is in it. if the target is larger than or equals nums[mid] and smaller than or equals nums[right], then we know the target can be found in this subarray. We are gonna use the right subarray in the next iteration.
that means we no longer need the left subarray, we can get rid of it by assign mid +1 to the left pointer.

if the target is not in the right subarray, Then it must be in the left one. that means we no longer need the right subway.
we can get rid of it by assign mid-1 to the right pointer.

// [mid , right] order subarray
 if(nums[mid] <target && target<= nums[right])
 {
     left = mid+1;
 }
 else //( target> nums[mid] || target< nums[right])
 {
      right = mid-1;
 }

Algorithms practice:leetcode 33. Search in Rotated Sorted Array,程序员英语面试,leetcode,算法
if the target is not in nums array, then we return -1 at the end.

we finish now.
It takes a while to clear your thought and find the correct solution. It’s not hard, but takes practice.

words

已整理

  1. integer [ˈɪntɪdʒə]: In mathematics, an integer is an exact whole number such as 1, 7, or 24 as opposed to a number with fractions or decimals.
    In C++, there are different types of variables (defined with different keywords), for example:
    int - stores integers (whole numbers), without decimals, such as 123 or -123
    double - stores floating point numbers, with decimals, such as 19.99 or -19.99

  2. array [əreɪ]: An array of objects is a collection of them that is displayed or arranged in a particular way.
    eg: Arrays are used to store multiple values in a single variable, instead of declaring separate variables for each value.(C++ https://www.w3schools.com/cpp/cpp_arrays.asp)

  3. ascending [əˈsɛndɪŋ] : If a group of things is arranged in ascending order, each thing is bigger, greater, or more important than the thing before it.
    I shall list my objections to the plan in ascending order of importance.我将会把我反对这个计划的理由按重要性从小到大一一列出。

  4. Descending [dɪˈsendɪŋ] :When a group of things is listed or arranged in descending order, each thing is smaller or less important than the thing before it.
    The results, ranked in descending order (= from the highest to the lowest) are as follows: 结果按递减顺序排列如下。

  5. distinct [dɪˈstɪŋkt]: values every element in the array is unique
    C++ Program to Counting distinct elements in an array.

  6. Prior [ˈpraɪə®] :

未整理

Initialization is the process of assigning a value to the Variable. [2]
Declare and initialize a variable with an integer value [3]
binary search 二分搜索算法
terminate 终止(进程)
subarray
ascending
iteration迭代
pointer 指针
we declare two int variables 申明变量
assign 0 to left point 赋值

ascending order 升序排列
distinct values every element in the array is unique
柯林斯词典
Prior to v-ing
passed to your function 补充例句 pass by value 按值传参(补全)
resulting :
0-indexed: Zero-based numbering is a way of numbering in which the initial element of a sequence is assigned the index 0, rather than the index 1 as is typical in everyday non-mathematical or non-programming circumstances. Under zero-based numbering, the initial element is sometimes termed the zeroth element,[1] rather than the first element; zeroth is a coined ordinal number corresponding to the number zero. In some cases, an object or value that does not (originally) belong to a given sequence, but which could be naturally placed before its initial element, may be termed the zeroth element. There is not wide agreement regarding the correctness of using zero as an ordinal (nor regarding the use of the term zeroth), as it creates ambiguity for all subsequent elements of the sequence when lacking context.

Zero-based array indexing is a way of numbering the items in an array such that the first item of it has an index of 0, whereas a one-based array indexed array has its first item indexed as 1.

Prior to being passed to your function

equation
decide on: to choose someone or something from a number of possible choices

In these graphs, the vertical axis represents the position of the object while the horizontal axis represents the time elapsed: the dependent variable, position, depends on the independent variable, time.

link

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

  1. C++ Variables
  2. https://www.learncpp.com/cpp-tutorial/variable-assignment-and-initialization/
  3. https://www.codeease.net/programming/python/Declaration-and-Initialization-of-Variables
  4. https://leetcode.com/problems/search-in-rotated-sorted-array/solutions/3879263/100-binary-search-easy-video-o-log-n-optimal-solution/

-1 negtive one

断句 <5词语, 一般动词加重
先将大框架,再一点点讲细节
读题框架
解题框架(算法)
在学生最少准备时,有所收获

我们将数字带入到公式中得到如下结果。(英语如何翻译?)

坐标的物理意义
变量的物理意义文章来源地址https://www.toymoban.com/news/detail-811447.html

  1. 看到题目:畏难,心理恐惧
  2. 看中文“旋转”,一下子就明白了,看英文有困难。理解英文困难

到了这里,关于Algorithms practice:leetcode 33. Search in Rotated Sorted Array的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • A Closer Look at Invalid Action Masking in Policy Gradient Algorithms 论文阅读

    原文链接:http://arxiv.org/abs/2006.14171 这篇文章证明了无效动作掩蔽可以看作是在计算动作概率分布时应用状态相关的可微函数来产生行为策略。接下来,设计了实验来比较无效动作掩饰和无效动作惩罚的性能。 无效动作惩罚:这是一种常见的方法,对无效动作给予负奖励,以

    2024年03月14日
    浏览(52)
  • Rust安全编码实践 Secure Coding Practices in Rust

    作者:禅与计算机程序设计艺术 Rust编程语言被称为可保证内存安全的系统编程语言,它在编译期间通过类型系统确保数据不出错。因此,Rust语言开发者需要掌握一些安全编码实践,如内存安全、访问控制、输入验证等。本文将对这些安全编码实践进行详细介绍,并结合Rus

    2024年02月04日
    浏览(40)
  • 【Leetcode Sheet】Weekly Practice 2

    给你一个整数 n ,请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。 提示: 1 = n = 10^5 【原始代码】: 【优化代码】 【其他思路】 将n转为字符串,例如n是1234,则char temp=‘1234’ 后续直接遍历strlen(temp),计算temp[i]-\\\'0’的值即可 给你一个 n x n 整数矩阵

    2024年02月12日
    浏览(31)
  • 【Leetcode Sheet】Weekly Practice 24

    给定平面上 n 对 互不相同 的点 points ,其中 points[i] = [xi, yi] 。 回旋镖 是由点 (i, j, k) 表示的元组 ,其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等( 需要考虑元组的顺序 )。 返回平面上所有回旋镖的数量。 提示: n == points.length 1 = n = 500 points[i].length == 2 -104 = xi, yi

    2024年01月18日
    浏览(34)
  • 【Leetcode Sheet】Weekly Practice 25

    给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。 提示: 链表中节点数目在范围 [0, 300] 内 -100 = Node.val = 100 题目数据保证链表已经按升序 排列 【模拟】 给你两个数字字符串 num1 和 num2 ,以及两个整数 max_s

    2024年01月22日
    浏览(33)
  • 【Leetcode Sheet】Weekly Practice 5

    给出一个含有不重复整数元素的数组 arr ,每个整数 arr[i] 均大于 1。 用这些整数来构建二叉树,每个整数可以使用任意次数。其中:每个非叶结点的值应等于它的两个子结点的值的乘积。 满足条件的二叉树一共有多少个?答案可能很大,返回 对 109 + 7 取余 的结果。 提示:

    2024年02月10日
    浏览(34)
  • 【Leetcode Sheet】Weekly Practice 3

    你会得到一个字符串 s (索引从 0 开始),你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出: indices , sources , targets 。 要完成第 i 个替换操作: 检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。 如果没有出现, 什么也不做 。 如果出现

    2024年02月11日
    浏览(44)
  • leetcode Median of Two Sorted Arrays

    Given two sorted arrays  nums1  and  nums2  of size  m  and  n  respectively, return  the median  of the two sorted arrays. The overall run time complexity should be  O(log (m+n)) . Example 1: Example 2: Constraints: nums1.length == m nums2.length == n 0 = m = 1000 0 = n = 1000 1 = m + n = 2000 -106 = nums1[i], nums2[i] = 106

    2023年04月08日
    浏览(39)
  • LeetCode83. Remove Duplicates from Sorted List

    Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well. Example 1: Input: head = [1,1,2] Output: [1,2] Example 2: Input: head = [1,1,2,3,3] Output: [1,2,3] Constraints: The number of nodes in the list is in the range [0, 300]. -100 = Node.val = 100 The list is guaranteed t

    2024年01月18日
    浏览(48)
  • Leetcode 82. Remove Duplicates from Sorted List II

    Remove Duplicates from Sorted List II Medium Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well. Example 1: Input: head = [1,2,3,3,4,4,5] Output: [1,2,5] Example 2: Input: head = [1,1,1,2,3] Output: [2,3] Constraints: The number of n

    2024年02月10日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包