在二維陣列的第二個元素上的紅寶石插值搜索

我在下面是在一維陣列上的簡單插值搜索$employee_list。該清單是由於退休而可能存在差距的僱員ID的有序列表。在二維陣列的第二個元素上的紅寶石插值搜索

def exist?(id) 
    lower = 0 
    upper = $employee_list.length - 1 
    while $employee_list[upper] != $employee_list[lower] && id >= $employee_list[lower] && id <= $employee_list[upper] 
     middle = lower + ((id - $employee_list[lower]) * (upper - lower)/($employee_list[upper] - $employee_list[lower])) 
     if id > $employee_list[middle] 
     lower = middle + 1 
     elsif id < $employee_list[middle] 
     upper = middle - 1 
     else 
     return true 
     end 
    end 
    return false 
end

現在我想將新元素添加到列表中，數組的第二個元素將包含員工的出生年份（即$employee_list[id][birthyear]）。我能夠根據生日年齡對數組進行排序，並且我想根據生日年份進行插值搜索，並返回具有特定生日的員工ID列表。

來源

2017-01-23 Benjamin

如果發佈了一個輸入（您的'employee_list'變量的一個例子）和$ employee_list陣列中的期望的輸出 – Bustikiller

@Bustikiller樣品元件將是[19，1992]這將是非常有用的。這意味着ID爲19的員工誕生於1992年。此外，該方法的返回值應該是一個包含所選年份中出生的所有員工ID的數組。 – Benjamin

這是一個修改後的版本。它返回一個id如果發現給定年份的員工，並且nil如果沒有找到員工。

如果您需要返回一年的多個ID，則需要插值搜索的修改版本。最後，插值搜索在均勻分佈的值下工作得最好。我想對於新生的員工來說情況並非如此。

def find_id_for_year(array, year) 
    lower = 0 
    upper = array.length - 1 
    while array[upper][1] != array[lower][1] && year >= array[lower][1] && year <= array[upper][1] 
    middle = lower + ((year - array[lower][1]) * (upper - lower)/(array[upper][1] - array[lower][1])) 
    if year > array[middle][1] 
     lower = middle + 1 
    elsif year < array[middle][1] 
     upper = middle - 1 
    else 
     return array[middle][0] 
    end 
    end 
end 

employee_list = Array.new(10) {|i| [i, rand(1990..2000)] }.sort_by(&:last) 

p employee_list 
#=> [[5, 1990], [8, 1990], [2, 1991], [9, 1991], [7, 1992], [0, 1995], [6, 1996], [4, 1998], [1, 1999], [3, 1999]] 
#=> [[8, 1990], [4, 1991], [5, 1991], [6, 1991], [2, 1996], [0, 1998], [1, 1998], [3, 1998], [7, 1999], [9, 2000]] 

p find_id_for_year(employee_list, 1992) 
#=> 7 
#=> nil

來源

2017-01-23 09:54:16

鑑於以下employee_list：

employee_list = [[19, 1992], [41, 1985], [12, 1958], [63, 1985]]

如果你想獲得你只需要選擇那些陣列，其最後一個元素是1985年誕生於1985年的員工ids，並得到過濾後的第一個元素陣列：

employee_list.select{|employee| employee.last == 1985}.map(&:first) 
# => [41, 63]

來源

2017-01-23 09:39:42 Bustikiller

在二維陣列的第二個元素上的紅寶石插值搜索

回答

相關問題