Stubborn 发表于 2020-6-7 19:56
瞅瞅18楼的，时间，空间复杂度是多少
你调用了Array.insert, 我好奇，会调用多少次。
赚小钱 发表于 2020-6-7 20:14
你调用了Array.insert, 我好奇，会调用多少次。
不超过2N,insert是成功的操作，不会反复的操作
Stubborn 发表于 2020-6-7 20:20
不超过2N,insert是成功的操作，不会反复的操作
无所谓超不超过 2N，既然正比于 N，那就是 O(N)
赚小钱 发表于 2020-6-7 20:21
无所谓超不超过 2N，既然正比于 N，那就是 O(N)
这个确实哈~不过第二个wihle会重复扫描数组，假如数组是 * n 会导致O(N^2), 二个wihle根据处理完的长度，长度又要根据任务长度来。最坏的情况应该就这样了，空间的话，O（1）应该是没问题的吧
Stubborn 发表于 2020-6-7 20:29
这个确实哈~不过第二个wihle会重复扫描数组，假如数组是 * n 会导致O(N^2), 二个wihle根据处理完 ...
有点复杂，大脑拒绝思考{:9_219:}
总之，我是不太相信有 O(1) 的做法的。
赚小钱 发表于 2020-6-7 20:32
有点复杂，大脑拒绝思考
总之，我是不太相信有 O(1) 的做法的。
{:10_255:}，不是O（1）是多少嘛{:10_272:}
在东边 发表于 2020-6-7 15:50
我是要按照元素出现次数排序，不是要按照元素大小排序
要想知道每个元素出现多少次，那至少得遍历一遍 ...
在原来容器上操作是没问题的，不需要新的容器
Stubborn 发表于 2020-6-7 20:34
，不是O（1）是多少嘛
如果，解决 1 个元素的数组，使用的**最少**额外空间，同样可以解决 1000000000000000000000 个元素的数组， 也就是说，额外空间的大小，与原数据规模，无任何相关性，才叫 O(1) 的空间复杂度。
赚小钱 发表于 2020-6-7 20:42
如果，解决 1 个元素的数组，使用的**最少**额外空间，同样可以解决 1000000000000000000000 个元素的数 ...
在原来数组操作，没有其他新的容器，算嘛{:10_319:}
Twilight6 发表于 2020-6-7 14:58
这样的空间复杂度算 O(1) 吧
这个0（1）是几年级教的
Python_Aaron 发表于 2020-6-7 18:21
新手看不懂，什么是空间复杂度？
同问
nahongyan1997 发表于 2020-6-7 20:59
这个0（1）是几年级教的
什么鬼几年级？？？ 这个是数据结构与算法的
赚小钱 发表于 2020-6-7 20:42
如果，解决 1 个元素的数组，使用的**最少**额外空间，同样可以解决 1000000000000000000000 个元素的数 ...
额外空间的大小，与原数据规模，无任何相关性。也就是说，不使用用额外的容器，对原数据做存储，映射的操作嘛.
Stubborn 发表于 2020-6-7 21:01
额外空间的大小，与原数据规模，无任何相关性。也就是说，不使用用额外的容器，对原数据做存储，映射的操 ...
可以使用，但是，长度为一个常数。
比如，在算法中，需要额外的5个位置来保存状态，申请一个固定长度的数据，这个长度，在编译期就可以确定。
这叫 O(1) 空间复杂度。
赚小钱 发表于 2020-6-7 21:15
可以使用，但是，长度为一个常数。
比如，在算法中，需要额外的5个位置来保存状态，申请一个固定长度的 ...
理解了，数据规模大小，不影响新的容器长度，大小。也算O（1）。{:10_287:}大佬，加个V呀
Stubborn 发表于 2020-6-7 21:38
理解了，数据规模大小，不影响新的容器长度，大小。也算O（1）。大佬，加个V呀
V 是啥
赚小钱 发表于 2020-6-7 21:41
V 是啥
微信呀，Vx简称V
@Stubborn @赚小钱
两位大佬，这个空间复杂度应该是 O(1) 吧{:10_254:}
def sort_by_frequency(nums):
min_count = min(map(nums.count, nums))
sorted_length = 0
cur_count = min_count
while sorted_length < len(nums):
for idx, num in enumerate(nums):
if idx >= sorted_length and nums.count(num) == cur_count:
# nums, nums = num, nums# 可以实现但不稳定
nums.insert(sorted_length, nums.pop(idx))
sorted_length += 1
cur_count += 1
在东边 发表于 2020-6-7 21:45
@Stubborn @赚小钱
两位大佬，这个空间复杂度应该是 O(1) 吧
看起来是的，牛逼。
{:10_256:}