精选50题之 33. 搜索旋转排序数组

本是古典何须时尚 2024-04-18 14:19 44阅读 0赞

### 腾讯精选练习（50 题）之 33. 搜索旋转排序数组 ###

*   *  原题目链接
     *  直接实现
     *  题目分析
     *  解题分析
     *  代码实现
     *  写在最后

## [原题目链接][Link 1] ##

假设按照升序排序的数组在预先未知的某个点上进行了旋转。  
( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。  
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。  
你的算法时间复杂度必须是 O(log n) 级别。

> 示例 1:  
> 输入: nums = \[4,5,6,7,0,1,2\], target = 0  
> 输出: 4

> 示例 2:  
> 输入: nums = \[4,5,6,7,0,1,2\], target = 3  
> 输出: -1

## 直接实现 ##

看到题目要求“时间复杂度必须是 O(log n) 级别”，说明应该采用二分查找，但是我还是想用O(1/2N)量级的循环遍历来尝试一下，会不会超时。

class Solution {
        
    public:
        int search(vector<int>& nums, int target) {
        
            if(nums.size() == 0 || nums.size() == 1 && nums[0] != target)
                return -1;
            if(nums.size() == 1 && nums[0] == target)
                return 0;
            if(target < nums[0])
            {
        
                for(int j = nums.size() - 1; j > 0; j--)
                {
        
                    if(target == nums[j])
                        return j;
                }
                return -1;
            }
            else
            {
        
                for(int j = 0; j < nums.size(); j++)
                {
        
                    if(target == nums[j])
                        return j;
                }
                return -1;
            }
        }
    };

复杂度分析：

*  时间复杂度：O(N)
 *  空间复杂度：O(1)

结果…  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
或许是因为实例并不是很变态，侥幸通过?

## 题目分析 ##

还是要用二分查找来进行实现。  
但是由于这是一个有序数组绕一点旋转得到的，mid =1/2(low + high) 可能四种情况，需要分情况讨论 想想就麻烦，那么能不能简化判断条件，少一些if…else…呢？

看到一个很短的实现，[LukeLee的解答][LukeLee]。简短而且涉及的异或运算符还从没用过，就学(用)它了?

## 解题分析 ##

其实还离不开对四种情况的讨论  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]

关键在这里, 太强了！  
![在这里插入图片描述][20190908215317448.png]  
再应用异或运算符，可想而知代码大幅缩减。

## 代码实现 ##

class Solution {
        
    public:
        int search(vector<int>& nums, int target) {
        
            int n = nums.size();
            if(n == 0 || n == 1 && nums[0] != target)
                return -1;
            if(n == 1 && nums[0] == target)
                return 0;
            int low = 0, high = n - 1;
            while(low < high)
            {
        
                int mid = (low + high) / 2;
                if((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
                    low = mid + 1;
                else
                    high = mid;
            }
            return low == high && nums[low] == target ? low : -1;   
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 2]  
复杂度分析：

*  时间复杂度：O(LogN)
 *  空间复杂度：O(1)

## 写在最后 ##

有的时候，有比较明确的思路未必好事，特别是习惯性的、定式的思维，这样可能就不会想到原来还有其他的“捷径”（只限于经验较少的前提下）。

贴一段if…else…判断的实现

class Solution {
        
    public:
        int search(vector<int>& nums, int target) {
        
            //第一步：寻找旋转点,最小元素的下标
            int beg = 0, end = nums.size() - 1, mid = (beg + end) / 2;
            int rotate_index = 0;
            if(nums.size() == 0){
        //特殊情况
                return -1;
            }
            while(beg <= end){
        
                mid = (beg + end) / 2;
                if(mid < nums.size() - 1 && nums[mid] > nums[mid + 1]){
        
                    rotate_index = mid + 1;
                    break;
                }
                else if(nums[mid] >= nums[beg]){
        //搜索右边序列
                    beg = mid + 1;
                }
                else{
        //搜索左边序列
                    end = mid - 1;
                }
            }
            if(target >= nums[0]){
        //目标值大于nums[0]，左边查找
                beg = 0, end = (rotate_index == 0?nums.size() - 1:rotate_index - 1);  
            }
            else{
        
                beg = rotate_index;
                end = nums.size() - 1;
            }
            while(beg <= end){
        
                mid = (beg + end) / 2;
                if(nums[mid] > target){
        
                    end = mid - 1;
                }
                else if(nums[mid] < target){
        
                    beg = mid + 1;
                }
                else{
        
                    return mid;
                }
            }
            if(beg > end){
        
                return -1;
            }
            else{
        
                return 0;
            }
        }
    };

[Link 1]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/fcb8ff65bbff4f829de8a565074c918a.png
[LukeLee]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-jian-solution-by-lukelee/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5052d0ef1b3742719a609c9742ff38c0.png
[20190908215317448.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f159ef6a201a4598ab5ad8a94a137e9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/600e1acce65c4527a2054ed912708aef.png