0

我有一本这样的字典：{a:0, b:1, c:2}. 实际上，字段名称和它在表中的顺序。我需要采用这种结构，以便（例如）如果 b 的位置变为 0，则结​​果为{b:0, a:1, c:2}. 如果 b 的位置变为 2 那么结果必须是{a:0, c:1, b:2}等等......

如何做到这一点？我不能使用内置函数（如果有的话），因为该字典中的每个字段都取自更复杂的结构。我基本上只能遍历这个字典，排序与否，并改变位置值。

我使用 Javascript/Coffeescript，但这没关系 - 我会欣赏任何语言的想法。

4

2 回答 2

2

考虑需要发生的事情：如果将某个值从 n 阶移动到 n' 阶，则实际上只有 n 阶和 n' 阶之间的值的顺序会发生变化。如果 n > n'，它们向下移动 1，如果 n < n'，它们向上移动 1。这是一些伪代码：

function(dict, name, newOrder)
{
    var oldOrder = dict[name];
    foreach((k, order) in dict)
    {
        if(order > oldOrder && order <= newOrder)
            dict[k]--;
        else if(order >= newOrder && order < oldOrder)
            dict[k]++;
    }
    dict[name] = newOrder;
}
于 2013-10-24T07:31:13.820 回答
1

这是一个不会遍历地图中所有元素的解决方案。
这很复杂，我认为它对小型数据集的速度并没有太大的提高。
抱歉，这不是正确的 javascript：

add = function(dict, vector, k)
{
    var size=len(vector);
    vector[size]=k;
    dict[k]=size;
}
swap(dict, vector, name, newOrder)
{   
    var oldOrder = dict[name]
    if(oldOrder < newOrder)
    {
        for(var i=oldOrder+1; i<=newOrder; i++)
        {  dict[vector[i]]--;
           vector[i-1]=vector[i];
        }
        dict[name]=newOrder;
        vector[newOrder]=dict[name]
    }
    else
    {
        for(var i=oldOrder-1; i>=newOrder; i--)
        {  dict[vector[i]]++;
           vector[i+1]=vector[i];
        }
        dict[name]=newOrder;
        vector[newOrder]=dict[name]
    }
}

解释：

add = function(dict, vector, k)
{
    var size=len(vector);
    vector[size]=k;
    dict[k]=size;
}
// vector: 0a 1b 2c 3d 4e
// map: a0 b1 c2 d3 e4

swap(dict, vector, name, newOrder)
{   
    // newOrder = 4

    var oldOrder = dict[name]
    // oldOrder = 1

    if(oldOrder < newOrder)
    {   
        // goes here
        for(var i=oldOrder+1; i<=newOrder; i++)
        {  
           // map: a0 b1 c2 d3 e4
           dict[vector[i]]--;
           // map: a0 b1 c1 d3 e4 //after one iteration

           // vector: 0a 1b 2c 3d 4e
           vector[i-1]=vector[i];
           // vector: 0a 1c 2c 3d 4e //after one iteration

        }
        // map: a0 b1 c1 d2 e3             
     // vector: 0a 1c 2d 3e 4e

        dict[name]=newOrder;
        vector[newOrder]=dict[name]

        // map: a0 b4 c1 d2 e3             
     // vector: 0a 1c 2d 3e 4b
    }
    else
    {
        for(var i=oldOrder-1; i>=newOrder; i--)
        {  dict[vector[i]]++;
           vector[i+1]=vector[i];
        }
        dict[name]=newOrder;
        vector[newOrder]=dict[name]
    }
}
于 2013-10-24T08:21:41.543 回答