求两个有序数组的第k大值

问题：100个运动员站成两排，每排已经按从高到低顺序排好，教练想找出身高排40位的队员，请问最少需要几次比较？（限制每次只能两个队员比身高）
分析: 也就是从两个有序数组中，找第k大的值。归并比较的话需要O(k)，所以这题希望找复杂更小的答案，比如O(logK)之类的。写个test先:

describe KthOfTwoSorted do
  let(:result) {subject.kth_of_two_sorted(n-1,x,y)}
  context "simple example" do
    let(:x) {[1,3,5,7,9]}
    let(:y) {[2,4,6,8,10]}
    let(:n) {8}
    let(:ans) {8}
    it "should find kth" do
      expect(result).to eq ans
    end
  end

make hands dirty

分析: 要小于O(k), 就不能访问所有元素，某些元素没被访问就可以排除了。

从第一队取出第15个人A，第2队取出第25个人B，如果A<B，可以发现包括第一队包括A在内的这15人都可以排除了（想想为什么）。
因此，我们每次从第一组取第k/2个，第二组第k-k/2个，这样一次比较就能排除一半的人，yes!

coding

于是，try伪码:

def kth(k, arrx, arry)
    return [arrx.first, arry.first].min if k==0

    xmid = k/2
    ymid = k-xmid
    if arrx[xmid] <= arry[ymid]
      kth(k-xmid-1, arrx[xmid+1..-1], arry)
    else
      kth(k-ymid-1, arrx, arry[ymid+1..-1])
    end
  end

扩充完整：

class KthOfTwoSorted
  def safe_kth(k, arrx, arry)
    return [arrx.first,arry.first].compact.min if k==0

    xmid = k/2
    ymid = k-(xmid+1)
    if arrx[xmid] <= arry[ymid]
      safe_kth(k-xmid-1, shift(arrx,xmid+1), arry)
    else
      safe_kth(k-ymid-1, arrx, shift(arry, ymid+1))
    end
  end

  def kth_of_two_sorted(k, arrx, arry)
    (arrx.size+arry.size).tap do |len|
      raise ArgumentError,"k should in range #{0..len}" unless 0<=k && k<len
    end

    arrx,arry = [arrx,arry].sort_by(&:size)
    if arrx.size < k
      arry.shift(k-arrx.size)
      k = arrx.size
    end

    safe_kth(k, arrx, arry)
  end

  private
  def shift(arr, n); arr.shift(n);arr end
end

测试代码:

require_relative '../kth_of_two_sorted_list'

shared_examples_for "find kth" do
  it "should find kth" do
    # k = n-1
    # ans = (x+y).sort[k]
    expect(result).to eq ans
  end
end

describe KthOfTwoSorted do
  let(:result) {subject.kth_of_two_sorted(n-1,x,y)}
  context "example normal" do
    let(:x) {[1,3,5,7,9]}
    let(:y) {[2,4,6,8,10]}
    let(:n) {8}
    let(:ans) {8}
    it_behaves_like "find kth"
  end
  context "when one is empty" do
    let(:x) {[]}
    let(:y) {(1..10).to_a}
    let(:n) {9}
    let(:ans) {9}
    it_behaves_like "find kth"
  end
  context "when one is too short" do
    let(:x) {[1,2,3]}
    let(:y) {(4..10).to_a}
    let(:n) {9}
    let(:ans) {9}
    it_behaves_like "find kth"
  end
  context "when repeat" do
    let(:x) {(1..100).select(&:odd?) + (101..200).to_a}
    let(:y) {(1..100).select(&:even?) + (101..200).to_a}
    let(:n) {200}
    let(:ans) {150}
    it_behaves_like "find kth"
  end
  context "when out of range" do
    let(:x) {[]}
    let(:y) {x}
    let(:n) {10}
    it "should raise error" do
      expect{result}.to raise_error(/k should in range/)
    end
  end
end