搜索旋转排序的数组Leetcode解决方案


难度级别 中等
经常问 土砖 阿里巴巴 亚马逊 Apple 彭博 ByteDance 思科 易趣 Expedia的 Facebook 高盛 谷歌 摩根大通 LinkedIn 微软 Nutanix Nvidia公司 神谕 贝宝 Paytm Salesforce的 Samsung ServiceNow 腾讯 特斯拉 到到网 Twitch 尤伯杯 签证 VMware的 沃尔玛实验室 雅虎 Yandex的 Zillow的 Zulily
排列 二进制搜索

考虑一个排序的数组,但是选择了一个索引,然后在该点旋转了数组。 现在,旋转数组后,您需要查找特定的目标元素并返回其索引。 如果该元素不存在,则返回-1。 该问题通常称为“在旋转排序的阵列Leetcode解决方案中搜索”。 因此,在这个问题中,我们提供了一些整数元素的数组,这些元素按我们不知道的特定索引进行排序和旋转。 除了数组,我们还需要找到一个特定的元素。

搜索旋转排序的数组Leetcode解决方案

array: [4,5,6,7,0,1,2]
target: 4
0

说明:由于要搜索的元素为4。该元素位于索引0处,因此我们返回目标的索引。

array: [4,5,6,7,0,1,2]
target: 3
-1

说明:由于该元素不存在于数组中,因此我们返回-1。

旋转排序数组中的蛮力搜索方法

问题“在旋转排序数组中搜索”要求我们在给定的旋转排序数组中找到目标元素的索引。 我们已经讨论了什么是旋转排序数组? 因此,人们想到的最简单的方法是尝试线性搜索。 在线性搜索中,我们只需遍历给定 排列 并检查当前元素是否是我们的目标元素。 如果当前元素是目标元素,则返回当前索引,否则返回-1。 该方法非常简单,但是由于它没有使用数组按单个索引排序和旋转的事实。 这种方法具有线性时间复杂度。

旋转排序数组Leetcode解决方案中的搜索代码

C ++代码

#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target) {
    int n = nums.size();
    for(int i=0;i<n;i++)
        if(nums[i] == target)
            return i;
    return -1;
}

int main(){
    vector<int> nums({4,5,6,7,0,1,2});
    cout<<search(nums, 4);
}
0

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int search(int[] nums, int target) {
        int n = nums.length;
        for(int i=0;i<n;i++)
            if(nums[i] == target)
                return i;
        return -1;
    }
    
    public static void main(String[] args){
    	int nums[] = {4,5,6,7,0,1,2};
    	System.out.println(search(nums, 4));
    }
}
0

复杂度分析

时间复杂度

上), 因为在最坏的情况下,目标元素可能会出现在数组的末尾。 因此,时间复杂度是线性的。

空间复杂度

O(1),因为我们没有关于每个元素的具体信息,并且使用了恒定数量的变量。 因此,空间复杂度是恒定的。

旋转排序数组中的优化搜索方法

前面提到的方法没有使用数组是旋转排序数组的事实。 因此,在这种方法中,我们尝试利用这一事实来减少时间复杂度。 考虑一下,如果我们有一个排序数组,我们会简单地使用 二进制搜索 但是万一这有点棘手。 在这里,我们还需要使用二进制搜索。 但是,如果我们使用二进制搜索,那么一旦进入数组的中间元素,我们如何知道要选择数组的哪一部分呢? 因为我们不能简单地遵循原始的二进制搜索算法,因为这是一个旋转的排序数组。 因此,对常规的二进制搜索进行了一些修改。

因此,通常在二进制搜索中,我们检查当前元素(中间索引处的元素)是否与目标相同,然后返回其索引。 此步骤在此保持不变。 除此之外,如果它们不相同,我们将检查枢轴是否位于[当前元素的右侧]或左侧。 如果位于右侧,则检查目标是否位于非旋转子数组中,如果它确实更新了高电平,则我们更新了低电平。 同样,如果枢轴位于左侧,则再次检查目标是否位于非旋转子数组中,我们更新低点,否则我们更新高点。 最后,如果我们退出循环,则可以确保目标不存在于给定数组中。

旋转排序数组Leetcode解决方案中用于搜索的优化代码

C ++代码

#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target) {
    int n = nums.size();
    int low = 0, high = n-1;
    while(low<=high){
        int mid = (low+high)/2;
        // check if the current element is target
        if(nums[mid] == target)
            return mid;
        // if the starting index of the search space has smaller element than current element
        else if(nums[low]<=nums[mid]){
            // if target lies in non-rotated search space (or subarray)
            if(target >= nums[low] && target < nums[mid])
                high = mid - 1;
            else
                low = mid + 1;
        } else {
            // if target lies in non-rotated subarray
            if(target>nums[mid] && target<=nums[high])
                low = mid + 1;
            else
                high = mid - 1;
        }
    }
    // if you couldn't find the target element until now then it does not exists
    return -1;
}
int main(){
    vector<int> nums({4,5,6,7,0,1,2});
    cout<<search(nums, 4);
}
0

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int search(int[] nums, int target) {
        int n = nums.length;
        int low = 0, high = n-1;
        while(low<=high){
            int mid = (low+high)/2;
            // check if the current element is target
            if(nums[mid] == target)
                return mid;
            // if the starting index of the search space has smaller element than current element
            else if(nums[low]<=nums[mid]){
                // if target lies in non-rotated search space (or subarray)
                if(target >= nums[low] && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else {
                // if target lies in non-rotated subarray
                if(target>nums[mid] && target<=nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        // if you couldn't find the target element until now then it does not exists
        return -1;
    }
    
    public static void main(String[] args){
    	int nums[] = {4,5,6,7,0,1,2};
    	System.out.println(search(nums, 4));
    }
}
0

复杂度分析

时间复杂度

O(log N), 因为我们已经使用二进制搜索来找到目标元素。 时间复杂度是对数的。

空间复杂度

O(1), 由于我们仅存储了一定数量的元素,因此空间复杂度是恒定的。