列表排名算法

发布于 2024-07-08 10:09:10 字数 242 浏览 6 评论 0原文

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

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

我想生成一个代表其排名的列表，在本例中为

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

数字实际上是类的有序列表的某些成员。请注意，列表的顺序不会改变，只是根据排名进行计数。

（这些数字代表 z 顺序，但可能还有其他用途）

原文

Given a list of numbers, which can be in any order, such as

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

I would like to produce a list which represents their rank, which in this case would be

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

The numbers are actually some member of an ordered list of classes. Note that the order of the list does not change, they just get counted according to their rank.

(these numbers represent a z-order, but there could be other uses)

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

深空失忆 2024-07-15 10:09:10

这是我的解决方案，尚未测试：

// 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)，如您所见......:(

This is my solution, untested as of yet:

// 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];

It is O(n^2), as you can see.... :(

回复收藏 0 原文

~没有更多了~