time-complexity 相关问题

这是原来的问题下面是我的超时代码：类解决方案{ 民众： int removeElement(向量& nums, int val) { 整数计数=0； for(int i=0;i 下面是我的超时代码： class Solution { public: int removeElement(vector<int>& nums, int val) { int count=0; for(int i=0;i<nums.size();i++){ if(nums[i]==val){ for(int j=i;j+1<nums.size();j++){ nums[j]=nums[j+1]; count+=1; } i--; } } return nums.size()-count; } }; 我尝试用一个变量来记录nums.size()的值，并将其作为for循环结构的条件判断。就成功了。但是我还是想知道.size()的使用时间以及它的内部代码和时间复杂度。 class Solution { public: int removeElement(vector<int>& nums, int val) { int count=0,size=nums.size(); for(int i=0;i<size;i++){ if(nums[i]==val){ for(int j=i;j+1<size;j++){ nums[j]=nums[j+1]; count+=1; } i--; size--; } } return size; } }; vector::size的时间复杂度是恒定的。但毫不奇怪，调用函数 5000 次 (size()) 或读取变量 5000 次 (size) 会有差异。实际上你很幸运，测试仅使用大小不超过 100 的向量，因为你的算法效率不高：在最坏的情况下它的时间复杂度为 O(𝑛²)。为了说明这一点，如果输入 nums 有 100 个元素，并且它们都等于给定的 val，那么你的算法将移动 99 个元素，然后是 98 个元素，然后是 97 个，...，所以总共会有1+2+3+..+99 次运动，即 4950 次。代码挑战中有一个提示：“元素的顺序可能会改变。”。这意味着，您可以从向量（的活动部分）中获取 last 值并用它覆盖该事件，而不是移动 val 出现后出现的所有值。然后减少 size 即可继续。这消除了您拥有的内部循环。这是这个想法的剧透实现： class Solution { public: int removeElement(vector& nums, int val) { int size = nums.size(); for (int i = 0; i < size; i++) { if (nums[i] == val) { size--; nums[i] = nums[size]; i--; } } return size; } };

arrays time-complexity timeout size

回答 1 投票 0

Google 面试问题 - 检查数组的所有子数组是否至少有一个唯一元素

我遇到了一个问题，我了解到这是一个谷歌面试问题。问题是：如果每个子数组至少包含一个频率为 1 的元素，那么数组就是好的。设计一个算法来 v...

arrays algorithm recursion time-complexity divide-and-conquer

回答 1 投票 0

这段带有滑动窗口的代码的时间复杂度是多少？

父 for 循环有 On ，而 while 循环有摊销 O n ？意思是我们认为它是O 1？还最小和最大操作它们将是好的，但在最坏的情况下又会再次打开？是O(n^3)吗？左=0

python arrays time-complexity sliding-window dsa

回答 1 投票 0

在线性时间内对具有重复元素的数组（给定其频率）进行排序

假设我们有一个包含 n 个整数的数组，并且我们知道某个整数 x 在数组中出现了 alpha 次。证明或反驳是否存在一种可以在线性时间内对该数组进行排序的算法： S...