033搜索旋转排序数组

  1 #include "000库函数.h"
  2 
  3 //自解  68ms  弱爆了
  4 //先找到最大值，然后确定目标值在最大值的左边还是右边
  5 //最后使用折中寻找法，找到目标值的位置,此方法应该满足复杂度不超过logn的要求
  6 class Solution {
  7 public:
  8     int search(vector<int>& nums, int target) {
  9         if (nums.size() == 0)return -1;
 10 
 11         int maxValue = *max_element(nums.begin(), nums.end());//最大值
 12         int maxPosition = max_element(nums.begin(), nums.end()) - nums.begin();//最大值的位置 
 13         if (target > maxValue)return -1;
 14         if (target == maxValue)return maxPosition;
 15         int i, j, t;
 16         if (target >= nums[0]) {
 17             i = 0;
 18             j = maxPosition;
 19         }
 20         else {
 21             i = maxPosition+1;
 22             j = nums.size() - 1;
 23         }        
 24         while (i <= j) {
 25             t = (i + j) / 2;
 26             if (target == nums[t])
 27                 return t;
 28             else if (target > nums[t])
 29                 i = t + 1;
 30             else
 31                 j = t - 1;
 32         }
 33         return -1;
 34     }
 35 };
 36 
 37 //这道题的关键在与，找到哪一部分是升序的
 38 //旋转数组有个特点，中间数的左右两边有一边一定是升序的，另一边就不一定了
 39 //此种解法满足复杂度logn的要求  20ms
 40 /*
 41 
 42 0　　1　　2　　 4　　5　　6　　7
 43 
 44 7　　0　　1　　 2　　4　　5　　6
 45 
 46 6　　7　　0　　 1　　2　　4　　5
 47 
 48 5　　6　　7　　 0　　1　　2　　4
 49 
 50 4　　5　　6　　7　　0　　1　　2
 51 
 52 2　　4　　5　　6　　7　　0　　1
 53 
 54 1　　2　　4　　5　　6　　7　　0
 55 
 56 
 57 */
 58 class Solution {
 59 public:
 60     int search(vector<int>& nums, int target) {
 61         if (nums.size() == 0)return -1;
 62         int i = 0, j = nums.size() - 1;
 63         while (i <= j) {
 64             int t = i + (j - i) / 2;//找到此时序列的中间位置
 65             if (target == nums[t])return t;
 66             if (nums[t] < nums[j]) {    //此时右边为升序
 67                 if (nums[t] < target&&target <= nums[j])//目标函数位于右边
 68                     i = t + 1;
 69                 else
 70                     j = t - 1;
 71             }
 72             else {
 73                 if (nums[i] < target && nums[t]>target)
 74                     j = t - 1;
 75                 else
 76                     i = t + 1;
 77             }
 78         }
 79         return -1;
 80     }
 81 };
 82 
 83 
 84 class Solution {
 85 public:
 86     int search(vector<int>& nums, int target) {
 87         if (nums.size() == 0)return -1;
 88         for (int i = 0; i < nums.size(); ++i) {
 89             if (target == nums[i])
 90                 return i;
 91         }
 92         return -1;
 93 
 94 
 95 
 96     }
 97 };
 98 
 99 void T033() {
100     Solution s;
101     vector<int>n;
102     n = { 3,1 };
103     cout << s.search(n, 1) << endl;
104     n = { 4,5,6,7,0,1,2 };
105     cout << s.search(n, 4) << endl;
106     n = { 4,5,6,7,0,1,2 };
107     cout << s.search(n, 7) << endl;
108     n = { 4,5,6,7,0,1,2 };
109     cout << s.search(n, 2) << endl;
110     n = { 4,5,6,7,0,1,2 };
111     cout << s.search(n, 0) << endl;
112 
113 }