美文网首页
求两个有序数组的第k大值

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

作者: davidhuangdw | 来源:发表于2014-11-29 19:22 被阅读1550次

问题: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

相关文章

  • 4. Median of Two Sorted Arrays

    两个有序数组的中位数,相当于寻找两个数组第k大的值,利用二分法进行查找,确定之后改变k的值与起始索引。 合并两个有...

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

    问题:100个运动员站成两排,每排已经按从高到低顺序排好,教练想找出身高排40位的队员,请问最少需要几次比较?(限...

  • [LeetCode By Python] 4. Median o

    一、题目 二、解题 1)题意 给出两个已经排好序的有序数组,求出两个数组的中间值(如果有两个值,则求两个数的平均值...

  • 探探后端开发面经

    两个有序数组例如a[](1,3,6,9)b[](4,5,6,7)求两个数组绝对值差最小值,思路并实现。 linux...

  • 算法分析 [最大/小值] 2019-02-28

    1. 数组,查找第k大值 215. 数组中的第K个最大元素(元素不重复无序) Kth Largest Elemen...

  • leetcode-0004

    题目: 4. 寻找两个有序数组的中位数 关键词:排序 折半查找 思路: 查找第k个数,每次查找二个数组的第k/2位...

  • BFPRT算法:求第K小或者第K大的数

    问题: 一个数组中求第k小或者第k大的数 思路(转自http://blog.csdn.net/liuxiao214...

  • 两个数组寻找第K大值

    标签(空格分隔): 数据结构与算法 题目: 任意给定两个已经排好序的数组A和B,求出A与B合并后第K大的值. 分析...

  • 兔兔森森面筋

    Intern 一个有序序列有N个数,随机替换其中k个,求复杂度< O(NlogN)的算法使替换后数组重新有序。St...

  • 2021-03-05富途社区C/C++后台一面

    两个有序数组求交集 两个数组A和B,A数组超大,内存装不下,求数组A和数组B的交集 字符串删空格 单向链表,给定链...

网友评论

      本文标题:求两个有序数组的第k大值

      本文链接:https://www.haomeiwen.com/subject/bqkgtttx.html