問題: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