求兩個有序數(shù)組的第k大值

問題:100個運動員站成兩排,每排已經(jīng)按從高到低順序排好,教練想找出身高排40位的隊員舔亭,請問最少需要幾次比較脖律?(限制每次只能兩個隊員比身高)
分析: 也就是從兩個有序數(shù)組中谢肾,找第k大的值。歸并比較的話需要O(k)小泉,所以這題希望找復(fù)雜更小的答案芦疏,比如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薪捍,可以發(fā)現(xiàn)包括第一隊包括A在內(nèi)的這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

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市息拜,隨后出現(xiàn)的幾起案子溉潭,更是在濱河造成了極大的恐慌,老刑警劉巖少欺,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件喳瓣,死亡現(xiàn)場離奇詭異,居然都是意外死亡赞别,警方通過查閱死者的電腦和手機畏陕,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來仿滔,“玉大人惠毁,你說我怎么就攤上這事∑橐常” “怎么了鞠绰?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長飒焦。 經(jīng)常有香客問我蜈膨,道長,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任翁巍,我火速辦了婚禮驴一,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘灶壶。我一直安慰自己肝断,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布驰凛。 她就那樣靜靜地躺著孝情,像睡著了一般。 火紅的嫁衣襯著肌膚如雪洒嗤。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天魁亦,我揣著相機與錄音渔隶,去河邊找鬼。 笑死洁奈,一個胖子當(dāng)著我的面吹牛间唉,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播利术,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼呈野,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了印叁?” 一聲冷哼從身側(cè)響起被冒,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎轮蜕,沒想到半個月后昨悼,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡跃洛,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年率触,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片汇竭。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡葱蝗,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出细燎,到底是詐尸還是另有隱情两曼,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布玻驻,位于F島的核電站合愈,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜佛析,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一益老、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧寸莫,春花似錦捺萌、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至披坏,卻和暖如春态坦,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背棒拂。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工伞梯, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人帚屉。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓谜诫,卻偏偏與公主長得像,于是被迫代替她去往敵國和親攻旦。 傳聞我的和親對象是個殘疾皇子喻旷,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪:刷leetcod...
    土汪閱讀 12,748評論 0 33
  • 1. 關(guān)于診斷X線機準(zhǔn)直器的作用牢屋,錯誤的是()且预。 (6.0 分) A. 顯示照射野 B. 顯示中心線 C. 屏蔽多...
    我們村我最帥閱讀 10,604評論 0 5
  • title: 推薦書 計算機心智之哲學(xué)原理id: 48categories: 讀書筆記date: 2015-08-...
    jeffleefree閱讀 489評論 0 0
  • 當(dāng)你毫無價值時,你自然而然被遺忘被嫌棄被放棄烙无,那種無端地放棄會讓你格外的絕望辣之。所以,你只能去創(chuàng)造價值皱炉,這是你的生存...
    梅自暗香來閱讀 220評論 0 0
  • 不知《老》怀估、《莊》,則不明達磨初祖所言中土之“大乘氣象”合搅;不知禪多搀,則難解老莊親證而難言之“虛無妙道”。夫言非吹灾部,反...
    Budhi閱讀 396評論 0 0