2

给定一个数字列表,可以按任何顺序排列,例如

3, -5, -1, 2, 7, 12, -8

我想制作一个代表他们排名的列表,在这种情况下是

4, 1, 2, 3, 5, 6, 0

这些数字实际上是有序列表中的某个成员。请注意,列表的顺序不会改变,它们只是根据他们的排名来计算。

(这些数字代表 z 顺序,但可能还有其他用途)

4

1 回答 1

0

这是我的解决方案,尚未经过测试:

// this will be our storage of the new z-order
int *tmpZ = new int[GetCount()];

int currentZ = INT_MIN;
int smallestIdx = -1;
int newZ = 0;
for (int passes = 0; passes < GetCount(); passes++)
{
    int smallestZ = INT_MAX;
    // find the index of the next smallest item
    for (int i = 0; i < GetCount(); i++)
    {
        if (GetAt(i)->m_zOrder > currentZ && GetAt(i) < smallestZ)
        {
            smallestIdx = i;
            smallestZ = GetAt(i)->m_zOrder;
        }
    }
    tmpZ[smallestIdx] = newZ;

    // prepare for the next item
    currentZ = smallestZ;
    newZ++;
    smallestIdx = -1;
}

// push the new z-order into the array
for (int i = 0; i < GetCount(); i++)
    GetAt(i)->m_zOrder = tmpZ[i];

如您所见,它是 O(n^2).... :(

于 2008-11-18T20:45:44.737 回答