2

我有一个排序数组，当服务器将元素提供给我时，我会在其中添加元素。我遇到的麻烦是确定在哪里放置我的新元素，然后将它放在同一个循环中

在 javascript 中，这看起来像这样

for(var i = 0; i < array.length; ++i){
   if( element_to_add < array[i]){
      array.splice(i,0,element_to_add);
      break;
   }
}

问题是在咖啡脚本中我无法访问计数器，所以我不能告诉它在所需的索引处拼接我的数组。

如何将元素添加到 CoffeeScript 中的排序数组？

4

3 回答 3

5

默认for循环也返回索引：

a = [1, 2, 3]
item = 2

for elem, index in a
    if elem >= item
        a.splice index, 0, item
        break

您可能想要改为进行二进制搜索。

于 2013-06-05T01:36:53.740 回答
2

如果您使用 Underscore.js（非常推荐用于这些类型的数组操作），_.sortedIndex它会返回一个值应该插入到数组中以保持有序的索引，它可以非常方便：

sortedInsert = (arr, val) ->
  arr.splice (_.sortedIndex arr, val), 0, val
  arr

如果您不使用下划线，那么自己制作sortedIndex也不是那么难；is 基本上是一个二分搜索（如果你想保持它的复杂性为 O(log n)）：

sortedIndex = (arr, val) ->
  low = 0
  high = arr.length
  while low < high
    mid = Math.floor (low + high) / 2
    if arr[mid] < val then low = mid + 1 else high = mid
  low
于 2013-06-05T02:30:21.687 回答
0

如果我理解正确，为什么不保存位置，像这样，

var pos=-1;
for(var i = 0; i < array.length; ++i){
   if( element_to_add < array[i]){

      pos=i; break;
   }
}
if(pos<0)
  array.push(element_to_add);
else array.splice(pos,0,element_to_add);
于 2013-06-05T01:29:55.293 回答