Ruby中已排序元素的原始索引
arr = [1,3,2,4] arr.sort #=> [1,2,3,4] 我想要一个数组[0, 2, 1, 3] arr.sort [0, 2, 1, 3] （ arr.sort顺序的原始索引）
使用Ruby 1.9.3有一种简单的方法吗？
谢谢
xs = [1, 3, 2, 4] original_indexes = xs.map.with_index.sort.map(&:last) #=> [0, 2, 1, 3]
arr=[1,3,2,4] p arr.map{|e| arr.sort.index(e)}
为了避免每次排序，更好的是：
arr=[1,3,2,4] arr_s = arr.sort p arr.map{|e| arr_s.index(e)}
更新
arr=[1,3,2,4] start_time = Time.now (1..100000).each do |i| arr.map{|e| arr.sort.index(e)} end elapsed = Time.now - start_time p elapsed xs = [1, 3, 2, 4] start_time = Time.now (1..100000).each do |i| xs.map.with_index.sort.map(&:last) end elapsed = Time.now - start_time p elapsed
得到了结果：
0.281736 0.504314
我测试了MRI Ruby 2.2.1p85（在Mac和CentOS上），tokland的解决方案返回了错误的结果：
xs = [8,3,2,7,5] xs.map.with_index.sort.map(&:last) #=> [2, 1, 4, 3, 0] # wrong
Yevgeniy Anfilofyev解决方案有效，但不支持非唯一数组：
arr = [8,3,2,7,5] arr_s = arr.sort arr.map{|e| arr_s.index(e)} #=> [4, 1, 0, 3, 2] # correct arr = [8,3,5,2,8,8,7,5] arr_s = arr.sort arr.map{|e| arr_s.index(e)} #=> [5, 1, 2, 0, 5, 5, 4, 2]
我来了这个：
arr = [8,3,5,2,8,8,7,5] index_order = [] arr.uniq.sort.each do |a| index_order += arr.each_index.select{|i| arr[i] == a } end r = [] index_order.each_with_index do |a, i| r[a] = i end r #=> [5, 1, 2, 0, 6, 7, 4, 3]
array = [6, 20, 12, 2, 9, 22, 17] sorted = array.sort indices = [] array.each do |n| index = (0...sorted.length).bsearch { |x| n <=> sorted[x] } indices << index end indices
此解决方案适用于O（nlogn）
(0..arr.size - 1).sort_by { |i| arr[i] }