合并两个没有内置Ruby函数的排序数组

k3fezbri  于 2022-09-21  发布在  Ruby
关注(0)|答案(3)|浏览(143)

我正在尝试合并两个已排序的数组,而不使用任何内置排序方法。这就是我到目前为止所拥有的。

def merge(array_1, array_2)
    i = 0
    k = 0
    merged_array = []
    while i < array_1.count && k < array_2.count
        while k < array_2.count && array_1[i] > array_2[k]
            merged_array << array_2[k]
            k += 1
        end
        merged_array << array_1[i]
        i += 1
    end
    merged_array
end

array_1 = [5,8,9,11]
array_2 = [4,6,7,12,13]

p merge(array_1, array_2)

输入为array_1 = [5,8,9,11]array_2 = [4,6,7,12,13],输出为[4, 5, 6, 7, 8, 9, 10, 11, 12, 13]。有没有人能解释一下为什么它不起作用。谢谢!

e5nszbig

e5nszbig1#

尝尝这个

def merge(array_1, array_2)
  return enum_for(__method__, array_1, array_2) unless block_given?

  a = array_1.each
  b = array_2.each
  loop { yield a.peek < b.peek ? a.next : b.next }

  # Your code is not working because the equivalent of these two lines
  # is missing. After you reach the end of one array you have to append
  # all remaining elements of the other array. I am doing this here by
  # just exhausting both enumerators, one of which is empty by now.

  loop { yield a.next }
  loop { yield b.next }
end

p merge([5, 8, 9, 11], [4, 6, 7, 12, 13]).entries

不需要跟踪指数。合并排序可以追溯到大型机和磁带的时代,因此只能使用枚举器来实现。

这是怎么回事?

  • each创建枚举器
  • peek返回下一个元素,而不推进枚举数
  • next返回包含枚举数的下一个元素
  • 上述两个函数在到达枚举数末尾时都会引发StopIteration
  • loop重复代码块,直到引发StopIteration
hc2pp10m

hc2pp10m2#

可以将一个数组的元素插入到另一个数组的副本中,使用数组#bsearch_index来确定第一个数组的每个元素应该放在哪里。

def merge(array_1, array_2)
  array_2.each_with_object(array_1.dup) { |n,arr|
     arr.insert(arr.bsearch_index { |i| i>n } || arr.size, n) }
end

array_1
  #=> [5, 8, 9, 11] 
array_2
  #=> [4, 6, 7, 12, 13, 14] 

merge(array_1, array_2)
  #=> [4, 5, 6, 7, 8, 9, 11, 12, 13, 14]

这是O(n1*log(N2)),n1和n2是两个数组的大小,因此循环在两个数组中较小的一个上会更有效率。

o2gm4chl

o2gm4chl3#

def merge_array(arr1, arr2)
  result = []
  l1, l2 = arr1.size, arr2.size
  m, n = 0, 0

  while true
    break if arr1[m].nil? || arr2[n].nil?

    if arr1[m] < arr2[n]
      result << arr1[m]
      m += 1
    else
      result << arr2[n]
      n += 1
    end
  end
  result += arr2[n..-1] if arr1[m].nil? && n < l2
  result += arr1[m..-1] if arr2[n].nil? && m < l1

  result
end

比较方法使用内核#循环

user     system      total        real

MERGE_ARRAY_LOOP 0.349738 0.002263 0.352001(0.352043)

MERGE_ARRAY_NEW 0.075791 0.002874 0.078665(0.078680)

相关问题