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

赚小钱

Stubborn 发表于 2020-6-7 19:56
瞅瞅18楼的，时间，空间复杂度是多少

你调用了  Array.insert, 我好奇，会调用多少次。

Stubborn

赚小钱 发表于 2020-6-7 20:14
你调用了  Array.insert, 我好奇，会调用多少次。

不超过2N,  insert是成功的操作，不会反复的操作

赚小钱

Stubborn 发表于 2020-6-7 20:20
不超过2N,  insert是成功的操作，不会反复的操作

无所谓超不超过 2N，既然正比于 N，那就是 O(N)

Stubborn

赚小钱 发表于 2020-6-7 20:21
无所谓超不超过 2N，既然正比于 N，那就是 O(N)

这个确实哈~不过第二个wihle会重复扫描数组，假如数组是[n, ] * n   会导致O(N^2), 二个wihle根据处理完的长度，长度又要根据任务长度来。最坏的情况应该就这样了，空间的话，O（1）应该是没问题的吧

赚小钱

Stubborn 发表于 2020-6-7 20:29
这个确实哈~不过第二个wihle会重复扫描数组，假如数组是[n, ] * n   会导致O(N^2), 二个wihle根据处理完 ...

有点复杂，大脑拒绝思考

总之，我是不太相信有 O(1) 的做法的。

Stubborn

赚小钱 发表于 2020-6-7 20:32
有点复杂，大脑拒绝思考

总之，我是不太相信有 O(1) 的做法的。

，不是O（1）是多少嘛

Stubborn

在东边 发表于 2020-6-7 15:50
我是要按照元素出现次数排序，不是要按照元素大小排序

要想知道每个元素出现多少次，那至少得遍历一遍 ...

在原来容器上操作是没问题的，不需要新的容器

赚小钱

Stubborn 发表于 2020-6-7 20:34
，不是O（1）是多少嘛

如果，解决 1 个元素的数组，使用的**最少**额外空间，同样可以解决 1000000000000000000000 个元素的数组， 也就是说，额外空间的大小，与原数据规模，无任何相关性，才叫 O(1) 的空间复杂度。

Stubborn

赚小钱 发表于 2020-6-7 20:42
如果，解决 1 个元素的数组，使用的**最少**额外空间，同样可以解决 1000000000000000000000 个元素的数 ...

在原来数组操作，没有其他新的容器，算嘛

nahongyan1997

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

这个0（1）是几年级教的

nahongyan1997

Python_Aaron 发表于 2020-6-7 18:21
新手看不懂，什么是空间复杂度？

同问

Twilight6

nahongyan1997 发表于 2020-6-7 20:59
这个0（1）是几年级教的

什么鬼几年级？？？ 这个是数据结构与算法的

Stubborn

赚小钱 发表于 2020-6-7 20:42
如果，解决 1 个元素的数组，使用的**最少**额外空间，同样可以解决 1000000000000000000000 个元素的数 ...

额外空间的大小，与原数据规模，无任何相关性。也就是说，不使用用额外的容器，对原数据做存储，映射的操作嘛.

赚小钱

Stubborn 发表于 2020-6-7 21:01
额外空间的大小，与原数据规模，无任何相关性。也就是说，不使用用额外的容器，对原数据做存储，映射的操 ...

可以使用，但是，长度为一个常数。
比如，在算法中，需要额外的5个位置来保存状态，申请一个固定长度的数据，这个长度，在编译期就可以确定。
这叫 O(1) 空间复杂度。

Stubborn

赚小钱 发表于 2020-6-7 21:15
可以使用，但是，长度为一个常数。
比如，在算法中，需要额外的5个位置来保存状态，申请一个固定长度的 ...

理解了，数据规模大小，不影响新的容器长度，大小。也算O（1）。大佬，加个V呀

赚小钱

Stubborn 发表于 2020-6-7 21:38
理解了，数据规模大小，不影响新的容器长度，大小。也算O（1）。大佬，加个V呀

V 是啥

Stubborn

赚小钱 发表于 2020-6-7 21:41
V 是啥

微信呀，Vx简称V

在东边

@Stubborn @赚小钱

两位大佬，这个空间复杂度应该是 O(1) 吧

1. def sort_by_frequency(nums):
   
2.     min_count = min(map(nums.count, nums))
   
3.     sorted_length = 0
   
4.     cur_count = min_count
   
5. 
   
6.     while sorted_length < len(nums):
   
7.         for idx, num in enumerate(nums):
   
8.             if idx >= sorted_length and nums.count(num) == cur_count:
   
9.                 # nums[sorted_length], nums[idx] = num, nums[sorted_length]  # 可以实现但不稳定
   
10.                 nums.insert(sorted_length, nums.pop(idx))
    
11.                 sorted_length += 1
    
12.         cur_count += 1
    

复制代码

赚小钱

在东边 发表于 2020-6-7 21:45
@Stubborn @赚小钱

两位大佬，这个空间复杂度应该是 O(1) 吧

看起来是的，牛逼。

笑叹，