对列表按照元素出现次数升序排序，要求空间复杂度为O(1)

在东边

有一个列表，假设为

nums = [1, 3, 2, 1, 3, 1]

按照元素出现次数升序排序，排序结果应该是

[2, 3, 3, 1, 1, 1]

可以在空间复杂度为 O(1) 的前提下，实现这样的排序算法吗？

下面这两种方法是不可行的：

1.

nums.sort(key=nums.count)

执行上面代码后，发现 nums 还是原来的 nums

看了下 Python 官方文档关于 list.sort 的介绍

里面提到

CPython implementation detail: 在一个列表被排序期间，尝试改变甚至进行检测也会造成未定义的影响。 Python 的 C 实现会在排序期间将列表显示为空，如果发现列表在排序期间被改变将会引发 ValueError。

排序期间列表显示为空，所以在对 nums 调用 sort 方法时，nums 始终为 []，nums.count 始终返回 0，因此 nums 未发生改变

2.

nums.sort(key=nums[:].count)

上面这行代码可以达到按元素出现次数排序，但由于使用列表的切片 nums[:]，创建了一份拷贝，空间复杂度不是 O(1)

Twilight6

这样的空间复杂度算 O(1) 吧

nums = [1, 2, 3, 1, 2, 1]
nums.sort()
nums.reverse()

永恒的蓝色梦想

基础

nums.sort(reverse=True)

Twilight6

永恒的蓝色梦想 发表于 2020-6-7 15:12
基础

学到了，我居然不知道还有这种用法

永恒的蓝色梦想

Twilight6 发表于 2020-6-7 15:17
学到了，我居然不知道还有这种用法

赚小钱

Twilight6 发表于 2020-6-7 14:58
这样的空间复杂度算 O(1) 吧

要看 sort 内部的实现。
基本上，时间复杂度在 O(nlogn) 的排序算法，空间复杂度都是不 O(1)。
而时间复杂度在 O(n^2) 的排序算法，空间复杂度是 O(1)。

在东边

永恒的蓝色梦想 发表于 2020-6-7 15:12
基础

看来这个 nums = [1, 2, 3, 1, 2, 1] 不太恰当

如果是下面这样呢

nums = [3, 2, 1, 3, 2, 3]

nums.sort(revere=True)

排完后，是 [3, 3, 3, 2, 2, 1]

可是按元素出现次数排序，应该是 [1, 2, 2, 3, 3, 3]

Twilight6

。。。才看见楼主说的是按出现次数排序

永恒的蓝色梦想

在东边 发表于 2020-6-7 15:20
看来这个 nums = [1, 2, 3, 1, 2, 1] 不太恰当

如果是下面这样呢

这个空间复杂度很低了

from collections import Counter
nums.sort(key=Counter(nums).__getitem__)

在东边

永恒的蓝色梦想 发表于 2020-6-7 15:31
这个空间复杂度很低了

假设这个列表长度为 n，里面每个元素都只出现 1 次（最坏情况）

那么使用 Counter 实例化后的对象长度也为 n

空间复杂度就是 O(n)

其实，我觉得吧，只要引入了新的容器对象，不管是 list，Counter 还是其他

空间复杂度都不可能是 O(1) 了

Stubborn

时间复杂度在 O(n^2) 的排序算法，空间复杂度是 O(1)。

可以很简单的实现啊

在东边

Stubborn 发表于 2020-6-7 15:42
时间复杂度在 O(n^2) 的排序算法，空间复杂度是 O(1)。

可以很简单的实现啊

我是要按照元素出现次数排序，不是要按照元素大小排序

要想知道每个元素出现多少次，那至少得遍历一遍，然后存在某个容器里，再根据次数排序吧

既然产生了新的容器，空间复杂度就不是 O(1) 了

或者是有什么我没想到的方法吧。。。

永恒的蓝色梦想

效率炸裂

def sort(list):
    flag=True
    robj=range(1,len(list))
    
    while flag:
        flag=False

        for i in robj:
            if list.count(list[i])<list.count(list[i-1]):
                list[i],list[i-1]=list[i-1],list[i]
                flag=True

赚小钱

无法实现
按照频率排序原列表，至少需要三步，
1. 统计每个元素的频率
2. 对频率排序
3. 将频率的顺序，映射到实际元素

所以，空间复杂度至少为 O(n)，时间复杂度为 O(nlogn)

靳子轩

我只会这两种方法，应该是O（1）

Stubborn

假设一个问题，

nums = [3, 2, 1, 3, 2, 3]

这个数组，第一个排序后，不管大小位置，我只把相同的排列到一起。产生如下序列

nums = [3, 3, 3, 2, 2,1]

出现次数升序排序,知道，最低是出现一次，换而言之，不用管其他的顺序

我扫描数组，把出现一次的，list.insert(index=0, obj)，

记录已经处理的长度len1，处理完一个+1.和一个“阶层”长度（default=0，当一个处理完，开始处理2次，更新为第一次出理完的长度）《处理的长度，用于记录下一‘’层；次该插入的位置，以及程序进度》《“阶层”的长度用于插入的位置》

Python_Aaron

新手看不懂，什么是空间复杂度？

Stubborn

def SorteTimeComplexityOne(Array):
    length = len(Array)
    idx = 2

    # TODO 数组排序，一样的放在一起。
    while length > idx:
        val = Array[idx]
        val_idx = Array.index(val)

        if val_idx < idx:
            del Array[idx]
            Array.insert(val_idx, val)

        idx += 1

    # TODO {
    #    Array: [1, 1, 1, 6, 2, 2, 2, 3, 3, 5, 5]
    #    success : 已经处理完的元素长度
    #    task ： 任务长度
    #    insert_idx ： 插入位置
    #    idxl : 左侧索引
    #    idxr : 右侧索引
    #  }
    success = 0
    insert_idx=0
    task = 1
    idxl = 0
    idxr = 1

    while length > success:

        if idxr < length and Array[idxl] == Array[idxr]:
            idxr += 1
        else:
            if task == idxr - idxl:

                while idxr - idxl:
                    val = Array[idxl]
                    del Array[idxl]
                    Array.insert(insert_idx, val)
                    idxl += 1
                    success += 1
            else:
                idxl = idxr

            if idxl >= length:
                idxl= idxr= insert_idx  = success
                task += 1

    print(Array)

v.ki

看不懂

Stubborn

赚小钱 发表于 2020-6-7 15:56
无法实现
按照频率排序原列表，至少需要三步，
1. 统计每个元素的频率

瞅瞅18楼的，时间，空间复杂度是多少