【Leetcode 每日一题】81. 搜索旋转排序数组 II

题目配景

已知存在一个按非降序排列的整数数组                                    n                         u                         m                         s                              nums                  nums，数组中的值不必互不相同。
在通报给函数之前，                                   n                         u                         m                         s                              nums                  nums 在预先未知的某个下标                                    k                                                   (                         0                         <                         =                         k                         <                         n                         u                         m                         s                         .                         l                         e                         n                         g                         t                         h                         )                              k\ (0 <= k < nums.length)                  k (0<=k<nums.length) 上进行了 旋转 ，使数组变为                                    [                         n                         u                         m                         s                         [                         k                         ]                         ,                         n                         u                         m                         s                         [                         k                         +                         1                         ]                         ,                         .                         .                         .                         ,                         n                         u                         m                         s                         [                         n                         −                         1                         ]                         ,                         n                         u                         m                         s                         [                         0                         ]                         ,                         n                         u                         m                         s                         [                         1                         ]                         ,                         .                         .                         .                         ,                         n                         u                         m                         s                         [                         k                         −                         1                         ]                         ]                              [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]                  [nums[k],nums[k+1],...,nums[n−1],nums[0],nums[1],...,nums[k−1]]（下标 从                                    0                              0                  0 开始 计数）。例如，                                   [                         0                         ,                         1                         ,                         2                         ,                         4                         ,                         4                         ,                         4                         ,                         5                         ,                         6                         ,                         6                         ,                         7                         ]                              [0,1,2,4,4,4,5,6,6,7]                  [0,1,2,4,4,4,5,6,6,7] 在下标                                    5                              5                  5 处经旋转后可能变为                                    [                         4                         ,                         5                         ,                         6                         ,                         6                         ,                         7                         ,                         0                         ,                         1                         ,                         2                         ,                         4                         ,                         4                         ]                              [4,5,6,6,7,0,1,2,4,4]                  [4,5,6,6,7,0,1,2,4,4]。
给你 旋转后 的数组                                    n                         u                         m                         s                              nums                  nums 和一个整数                                    t                         a                         r                         g                         e                         t                              target                  target，请你编写一个函数来判定给定的目标值是否存在于数组中。假如                                    n                         u                         m                         s                              nums                  nums 中存在这个目标值                                    t                         a                         r                         g                         e                         t                              target                  target，则返回                                    t                         r                         u                         e                              true                  true，否则返回                                    f                         a                         l                         s                         e                              false                  false。
你必须尽可能淘汰整个操纵步骤。
数据约束

•                                         1                            ≤                            n                            u                            m                            s                            .                            l                            e                            n                            g                            t                            h                            ≤                            5000                                  1 \le nums.length \le 5000                     1≤nums.length≤5000
  
•                                         −                            1                                       0                               4                                      ≤                            n                            u                            m                            s                            [                            i                            ]                            ≤                            1                                       0                               4                                            -10 ^ 4 \le nums \le 10 ^ 4                     −104≤nums≤104
  
• 标题数据保证                                         n                            u                            m                            s                                  nums                     nums 在预先未知的某个下标上进行了旋转
  
•                                         −                            1                                       0                               4                                      ≤                            t                            a                            r                            g                            e                            t                            ≤                            1                                       0                               4                                            -10 ^ 4 \le target \le 10 ^ 4                     −104≤target≤104
  

解题过程

这题是在 搜索旋转排序数组 的基础上增加了元素可重复这个条件，仍旧可以参考无重复元素的实现，先找到最小值，再到相应的部分数组中去找结果。
然而之前的二分答案法是每次与数组的末了一个元素比较大小，假如碰到当前元素与数组中末了一个元素重复的情况，就没有办法确定要往谁人方向继续实行了。
考虑到假如有重复元素出现上述情况，它们会在旋转之后分布在数组两头。
这时候可以反复比较范围左界限的元素和数组中末了一个元素，发现重复时就将范围中的首个元素去掉。
可能会出现两种情况，去掉的这个是要查找的目标，那它还有一个重复值在数组末尾，不影响结果；去掉的这个不是要查找的目标，那就无所谓了，也不影响结果。
这道题属于是经典的为了考知识点而一味地加限定，评价为出题把脑子出坏了。
道理很简单，去掉重复元素使得范围上可用二分查找这个过程，时间复杂度是                                    O                         (                         N                         )                              O(N)                  O(N) 这个量级的。
这就导致了，整个算法是无法达到                                    O                         (                         l                         o                         g                         N                         )                              O(logN)                  O(logN) 这样的程度了。
既然云云，还费劲巴拉的二分什么二分，直接遍历数组同样也只是必要                                    O                         (                         N                         )                              O(N)                  O(N) 的时间。
具体实现

二分查找

1. class Solution {
2.     public boolean search(int[] nums, int target) {
3.         int n = nums.length;
4.         int left = 0, right = n - 1;
5.         // 去掉二分范围内首尾的重复元素，注意 left != n - 1 这个条件，别把所有元素都去掉了
6.         while (left != n - 1 && nums[left] == nums[n - 1]) {
7.             left++;
8.         }
9.         // Leetcode 33.搜索旋转排序数组
10.         int minIndex = findMin(nums, left, right);
11.         if (target > nums[n - 1]) {
12.             return binarySearch(nums, target, 0, minIndex);
13.         }
14.         return binarySearch(nums, target, minIndex, n);
15.     }
17.     // Leetcode 153.找到数组中的最小值
18.     private int findMin(int[] nums, int left, int right) {
19.         int n = nums.length;
20.         while(left < right) {
21.             int mid = left + ((right - left) >> 1);
22.             if (nums[mid] > nums[n - 1]) {
23.                 left = mid + 1;
24.             } else {
25.                 right = mid;
26.             }
27.         }
28.         return left;
29.     }
31.     // Leetcode 35.搜索插入位置
32.     private boolean binarySearch(int[] nums, int target, int left, int right) {
33.         while (left < right) {
34.             int mid = left + ((right - left) >> 1);
35.             if (nums[mid] < target) {
36.                 left = mid + 1;
37.             } else {
38.                 right = mid;
39.             }
40.         }
41.         return nums[left] == target;
42.     }
43. }

复制代码

直接遍历

1. class Solution {
2.     public boolean search(int[] nums, int target) {
3.         for (int num : nums) {
4.             if (num == target) {
5.                 return true;
6.             }
7.         }
8.         return false;
9.     }
10. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。