Search in Rotated Sorted Array II

Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

在一个数组中查找，其中元素允许重复。对时间复杂性的影响？最基本的方法就是暴力依次搜索，时间复杂度为O(n),由于是被旋转对调的数组，当其值没有重复时二分查找。当值重复时，target与nums[mid]大小不能判断其在左边还是右边。例如nums[m]>=nums[1],1~m之间不一定是递增。。两种情况。nums[m] > nums[1] 或者nums[m] > nums[1] .

//二分查找变种bool binSearch(vector
     
      & nums,int target) {    int first = 0;    int last = nums.size() - 1;    while (first != last) {        int mid = first + (last - first) / 2;        if (nums[mid] == target) return true;                if (nums[first] < nums[mid]) {                    //前半部分判断            if (nums[first] < target && target < nums[mid])                    last = mid;            else                first = mid + 1;        }         else if (nums[first] > nums[mid]) {            if (nums[mid] < target && nums[last] > target)                first = mid + 1;            else                last = mid;        }        else            first++;    }    return false;}
     

Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log(m + n)).

查找两个有序数组中的中位数，类似的还有查找两个数组中的最大数。

一种简单的方法就是申请一个新的数组，长度为m+n,把A和B排序求出中位数，空间复杂度会超过限制应该。

另一种方法是用两个指针，point_A和point_B，分别指向A，B，比较两者大小，较小的一个++，依次比较。降低了空间复杂度。时间复杂度和K值有关。

leetcode题解的解法更经典：寻找第K大个元素，每次删除不在的一部分，减少时间复杂度：假设A和B分别有 A 和B个元素，都大于k/2个元素，比较A和B的K/2元素大小

有三种情况：

A[k/2-1] < B [K/2-1]; 这时候其最K大个值不可能在A[0]~A[k/2]之间，删除这部分；

A[k/2-1] > B [K/2-1]; 这时候其最K大个值不可能在B[0]~B[k/2]之间，删除这部分；

A[k/2-1] == B [K/2-1];时，这说明已经找到第K个元素，直接返回A[k/2-1]或者B[k/2-1]。

一个递归的过程。当Ａ和B为空时，返回A[k-1]或者B[k-1]；当K = 1时，返回min{A[0], B[0]}; A[k/2-1] == B [K/2-1];时，这说明已经找到第K个元素，直接返回A[k/2-1]或者B[k/2-1]。

#include 
     
      #include 
      
       #include 
       
        using namespace std;int find_kth(const vector
        
         ::const_iterator A, int m,         const vector
         
          ::const_iterator B, int n, int k) {    //假设m一直是<= n    if (m > n) return find_kth(B, n, A, m, k);    if (m == 0) return *(B + k - 1);    if (k == 1) return min(*A, *B);    int ia = min(k / 2, m), ib = k - ia;    if (*(A + ia - 1) < *(B + ib - 1))        return find_kth(A + ia, m - ia, B, n, k - ia);    else if (*(A + ia - 1) > *(B + ib - 1))        return find_kth(A, m, B + ib, n - ib, k - ib);    else        return A[ia - 1];}double findMediaArray(vector
          
           & A,vector
           
            & B) { int m = A.size(); int n = B.size(); int total = m + n; if (total & 0x1) return find_kth(A.begin(), m, B.begin(), n, total / 2 + 1); else return (find_kth(A.begin(), m, B.begin(), n, total / 2) + find_kth(A.begin(), m, B.begin(), n, total / 2 + 1)) / 2;}