对列表按照元素出现次数升序排序，要求空间复杂度为O(1)
本帖最后由 在东边 于 2020-6-7 15:39 编辑有一个列表，假设为
nums =
按照元素出现次数升序排序，排序结果应该是
可以在空间复杂度为 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 于 2020-6-7 15:07 编辑
{:10_245:}
这样的空间复杂度算 O(1) 吧
nums =
nums.sort()
nums.reverse() 基础nums.sort(reverse=True) 永恒的蓝色梦想 发表于 2020-6-7 15:12
基础
学到了{:10_256:}，我居然不知道还有这种用法 Twilight6 发表于 2020-6-7 15:17
学到了，我居然不知道还有这种用法
{:10_277:} Twilight6 发表于 2020-6-7 14:58
这样的空间复杂度算 O(1) 吧
要看 sort 内部的实现。
基本上，时间复杂度在 O(nlogn) 的排序算法，空间复杂度都是不 O(1)。
而时间复杂度在 O(n^2) 的排序算法，空间复杂度是 O(1)。 永恒的蓝色梦想 发表于 2020-6-7 15:12
基础
看来这个 nums = 不太恰当{:10_277:}
如果是下面这样呢
nums =
nums.sort(revere=True)
排完后，是
可是按元素出现次数排序，应该是 。。。才看见楼主说的是按出现次数排序 在东边 发表于 2020-6-7 15:20
看来这个 nums = 不太恰当
如果是下面这样呢
这个空间复杂度很低了{:10_277:}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) 了 时间复杂度在 O(n^2) 的排序算法，空间复杂度是 O(1)。
可以很简单的实现啊 Stubborn 发表于 2020-6-7 15:42
时间复杂度在 O(n^2) 的排序算法，空间复杂度是 O(1)。
可以很简单的实现啊
我是要按照元素出现次数排序，不是要按照元素大小排序
要想知道每个元素出现多少次，那至少得遍历一遍，然后存在某个容器里，再根据次数排序吧
既然产生了新的容器，空间复杂度就不是 O(1) 了
或者是有什么我没想到的方法吧。。。{:10_266:} {:10_277:}效率炸裂def sort(list):
flag=True
robj=range(1,len(list))
while flag:
flag=False
for i in robj:
if list.count(list)<list.count(list):
list,list=list,list
flag=True 无法实现
按照频率排序原列表，至少需要三步，
1. 统计每个元素的频率
2. 对频率排序
3. 将频率的顺序，映射到实际元素
所以，空间复杂度至少为 O(n)，时间复杂度为 O(nlogn) 我只会这两种方法，应该是O（1） 本帖最后由 Stubborn 于 2020-6-7 17:11 编辑
假设一个问题，
nums =
这个数组，第一个排序后，不管大小位置，我只把相同的排列到一起。产生如下序列
nums =
出现次数升序排序,知道，最低是出现一次，换而言之，不用管其他的顺序
我扫描数组，把出现一次的，list.insert(index=0, obj)，
记录已经处理的长度len1，处理完一个+1.和一个“阶层”长度（default=0，当一个处理完，开始处理2次，更新为第一次出理完的长度）《处理的长度，用于记录下一‘’层；次该插入的位置，以及程序进度》《“阶层”的长度用于插入的位置》
新手看不懂，什么是空间复杂度？{:10_269:}
挣个10鱼币，不容易啊！{:10_295:}
本帖最后由 Stubborn 于 2020-6-7 20:20 编辑{:10_272:}
def SorteTimeComplexityOne(Array):
length = len(Array)
idx = 2
# TODO 数组排序，一样的放在一起。
while length > idx:
val = Array
val_idx = Array.index(val)
if val_idx < idx:
del Array
Array.insert(val_idx, val)
idx += 1
# TODO {
# Array:
# 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 == Array:
idxr += 1
else:
if task == idxr - idxl:
while idxr - idxl:
val = Array
del Array
Array.insert(insert_idx, val)
idxl += 1
success += 1
else:
idxl = idxr
if idxl >= length:
idxl= idxr= insert_idx= success
task += 1
print(Array) 看不懂{:10_277:} 赚小钱 发表于 2020-6-7 15:56
无法实现
按照频率排序原列表，至少需要三步，
1. 统计每个元素的频率
瞅瞅18楼的，时间，空间复杂度是多少{:10_262:}