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

在东边

有一个列表，假设为

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

复制代码

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

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

复制代码

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

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

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.

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

复制代码

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

Twilight6

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

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

复制代码

永恒的蓝色梦想

基础

1. 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] 不太恰当

如果是下面这样呢

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

复制代码

1. 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] 不太恰当

如果是下面这样呢

这个空间复杂度很低了

1. from collections import Counter
   
2. 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) 了

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

永恒的蓝色梦想

效率炸裂

1. def sort(list):
   
2.     flag=True
   
3.     robj=range(1,len(list))
   
4.    
   
5.     while flag:
   
6.         flag=False
   
7. 
   
8.         for i in robj:
   
9.             if list.count(list[i])<list.count(list[i-1]):
   
10.                 list[i],list[i-1]=list[i-1],list[i]
    
11.                 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

1. def SorteTimeComplexityOne(Array):
   
2.     length = len(Array)
   
3.     idx = 2
   
4. 
   
5.     # TODO 数组排序，一样的放在一起。
   
6.     while length > idx:
   
7.         val = Array[idx]
   
8.         val_idx = Array.index(val)
   
9. 
   
10.         if val_idx < idx:
    
11.             del Array[idx]
    
12.             Array.insert(val_idx, val)
    
13. 
    
14.         idx += 1
    
15. 
    
16.     # TODO {
    
17.     #    Array: [1, 1, 1, 6, 2, 2, 2, 3, 3, 5, 5]
    
18.     #    success : 已经处理完的元素长度
    
19.     #    task ： 任务长度
    
20.     #    insert_idx ： 插入位置
    
21.     #    idxl : 左侧索引
    
22.     #    idxr : 右侧索引
    
23.     #  }
    
24.     success = 0
    
25.     insert_idx=0
    
26.     task = 1
    
27.     idxl = 0
    
28.     idxr = 1
    
29. 
    
30.     while length > success:
    
31. 
    
32.         if idxr < length and Array[idxl] == Array[idxr]:
    
33.             idxr += 1
    
34.         else:
    
35.             if task == idxr - idxl:
    
36. 
    
37.                 while idxr - idxl:
    
38.                     val = Array[idxl]
    
39.                     del Array[idxl]
    
40.                     Array.insert(insert_idx, val)
    
41.                     idxl += 1
    
42.                     success += 1
    
43.             else:
    
44.                 idxl = idxr
    
45. 
    
46.             if idxl >= length:
    
47.                 idxl= idxr= insert_idx  = success
    
48.                 task += 1
    
49. 
    
50.     print(Array)

复制代码

v.ki

看不懂

Stubborn

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

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