给定一个数字列表,可以按任何顺序排列,例如
3, -5, -1, 2, 7, 12, -8
我想制作一个代表他们排名的列表,在这种情况下是
4, 1, 2, 3, 5, 6, 0
这些数字实际上是有序列表中的某个成员。请注意,列表的顺序不会改变,它们只是根据他们的排名来计算。
(这些数字代表 z 顺序,但可能还有其他用途)
这是我的解决方案,尚未经过测试:
// 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).... :(