学步园

  最近各种原因一直看论文做ppt，觉得还是得养成刷题的习惯，保持思维的活跃度，而且可以多手准备。

  很多人推荐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<Integer> arr1, ArrayList<Integer> 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<n;i++)
			arr1.add(arr1.get(i-1) + ranGen.nextInt(100));
		for(int i=1;i<m;i++)
			arr2.add(arr2.get(i-1) + ranGen.nextInt(100));
		
	}
	//For testing, generate two fixed number arrays.
	public static void GenerateFixedSortedArrs(ArrayList<Integer> arr1, ArrayList<Integer> 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<a1.length;i++ )
			arr1.add(a1[i]);
		
		for(int i=0;i<a2.length;i++ )
			arr2.add(a2[i]);
	}
	//For testing, show the array
	public static void ShowArr(ArrayList<Integer> arr)
	{
		for(int i=0;i<arr.size();i++)
		{
			System.out.print(arr.get(i) + ", ");
		}
		System.out.println();
	}
	
	//O(k) algorithm
	public static int KthValueFromSortedArrs_Linear(ArrayList<Integer> arr1, ArrayList<Integer> 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;)
			for(int j=0;j<k;)
			{
				int arr1_i = (i<arr1.size()) ? arr1.get(i) : MAX;
				int arr2_j = (j<arr2.size()) ? arr2.get(j) : MAX;
				
				if(arr1_i < arr2_j)
				{
					c++;
					if(c==k)
						return arr1_i;
					i++;
				}
				else if(arr2_j < arr1_i)
				{
					c++;
					if(c==k)
						return arr2_j;
					j++;
				}
				else if(arr1_i == arr2_j)
				{
					c+=2;
					if(c>=k)
						return arr1_i;
					i++;
					j++;
				}
			}
		
		return -1;
	}
	
	//O(log(k)) algorithm
	public static int KthValueFromSortedArrs_Log(ArrayList<Integer> arr1, ArrayList<Integer> 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<arr1.size())? arr1.get(i+1) : MAX;
			
			if(j >= 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.size())? arr2.get(j+1) : MAX;

			if (arr1_i_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<Integer> arr1 = new ArrayList<Integer>();
			ArrayList<Integer> arr2 = new ArrayList<Integer>();
			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!");
		
 	}

}