求两个排好序的数组中的第k小数字

很多人推荐LeetCode，第一次玩，OJ的题目太少。去看了讨论版，随便选了道容易上手的，给定两个排好序的数组，找出第k小的数字。

O( (m+n)log(m+n))的算法应该没人会用吧。

O(k)的算法应该很多人都能想到。

O(log(k))的算法有点难想到。不过想通了发现思维也很简单。第k小的数字为x，那么数组1一定有i个数字小于x，数组2一定有j个数字小于x，注意i+j=k-1。因为k已知，所以我们只要搜索i即可。然后我们可以想象到，如果元素array1[i+1]为两个数组的并的第k小的数字的话，那么它满足 arrary1[i+1] >= array2[j] && array1[i+1]<=array2[j+1]。同理如果array2[j+1]为两个数组的并的第k小的数字的话，那么它满足 arrary2[j+1] >= array1[i] && array2[j+1]<=array1[i+1]。二分搜索数组1的i，并对照数组2对应的j，如果array1[i]的值太大，搜索数组1的i的前半区间，否则搜索后半区间。这个二分有点难描述，具体可以参考：

http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of. html

实现了O(k)和O(log(k))的代码加测试代码：

import java.util.*;  
  
public class main {  
    //Generate two random arrays.  
    public static void GenerateRanSortedArrs(ArrayList arr1, ArrayList arr2)  
    {  
        Random ranGen = new Random();  
          
        int n = ranGen.nextInt(100);  
        int m = ranGen.nextInt(100);  
          
        arr1.add(ranGen.nextInt(10));  
        arr2.add(ranGen.nextInt(10));  
          
        for(int i=1;i arr1, ArrayList arr2)  
    {  
        int[] a1= new int[]{5,5,5,5,5,5};  
        int[] a2= new int[]{5,5,5,5,5,5,5};  
          
        for(int i=0;i arr)  
    {  
        for(int i=0;i arr1, ArrayList arr2, int k)  
    {  
        if(k > arr1.size() + arr2.size())  
            return -1;  
      
        int MAX = 1<<31 -1 ;  
        int MIN = 1<<31;  
          
        int c =0;  
        for(int i=0;i





=k)  
                        return arr1_i;  
                    i++;  
                    j++;  
                }  
            }  
          
        return -1;  
    }  
      
    //O(log(k)) algorithm  
    public static int KthValueFromSortedArrs_Log(ArrayList arr1, ArrayList arr2, int k)  
    {  
        if(k > arr1.size() + arr2.size())  
            return -1;  
        int MAX = 1<<31-1;  
        int MIN = 1<<31;  
        int i,j;//i+j == k-1  
        int left=0,right=k-1;  
        while(true)  
        {     
            if(right >= left)  
                i = (left+right)/2;  
            else  
                i = -1;  
            j = k-1-1-1-i;  
              
            if(i >= arr1.size())//it means there is not enough i  
            {  
                right = i - 1;  
                continue;  
            }  
            int arr1_i = (i>=0)  arr1.get(i) : MIN;   
            int arr1_i_1 = (i+1= arr2.size())//it means there is no enough j, so i must get bigger.  
            {  
                left = i + 1;  
                continue;  
            }  
            int arr2_j = (j>=0)  arr2.get(j) : MIN;  
            int arr2_j_1 = (j+1= arr2_j  
                    && arr1_i_1 <= arr2_j_1)  
                return arr1_i_1;  
  
            else if (arr2_j_1 >= arr1_i  
                    && arr2_j_1 <= arr1_i_1)  
                return arr2_j_1;  
  
            else if (arr1_i > arr2_j) {  
                right = i - 1;  
            }  
  
            else if (arr1_i < arr2_j) {  
                left = i+1;  
            }  
        }  
          
    }  
      
    public static void main(String[] args)  
    {  
          
  
        for(int i=0;i<1000;i++)  
        {  
            ArrayList arr1 = new ArrayList();  
            ArrayList arr2 = new ArrayList();  
            GenerateRanSortedArrs(arr1,arr2);  
              
              
            for(int k=3;k<=arr1.size()+arr2.size();k++)  
            {  
              int k1 = KthValueFromSortedArrs_Linear(arr1,arr2,k) ;  
          
              int k2 = KthValueFromSortedArrs_Log(arr1,arr2,k) ;  
          
              //System.out.println(k1 + " " + k2);  
              if(k1 != k2)  
              {  
                 ShowArr(arr1);  
                 ShowArr(arr2);  
                 System.out.println(k1 + " " + k2);  
              }  
            }  
        }  
          
        System.out.println("Finished Running All The Demos!");  
          
    }  
  
}