Leetcode#315: 大家帮忙看看

楼主代码不是二分复杂度

二分是不能有递归的，你这个二分不是O(logn)的

你这个内循环+外循环双循环是O(n^2)

格林匹施ZELQ 发表于 2020-09-29 23:06:25
add在特定位置的复杂度是O(n)，你的方法还是平方的复杂度

谢谢，我也怀疑过。特定位置加的时候，找到那个特定位置-》要遍历走到特定位置，所以是O(n).

不过我这两个O(n*n)的解法，英文版的leetcode, 二分的不过，另一个过了，也挺有意思的，应该二分更超时。

ahao99 发表于 2020-9-30 15:07
二分是不能有递归的，你这个二分不是O(logn)的

这不是问题的关键所在，下面这个不是递归版，同样超时。问题是add()在特定位置是O(n), 二分那个找插入位置index是O(logn)， 所以总耗时O(n*(n+logn))=O(n*n)

1. public List<Integer> countSmaller(int[] nums)
   
2. {
   
3.         int size = nums.length;
   
4.         List<Integer> ans= new ArrayList<>();
   
5.         List<Integer> list = new LinkedList<>();
   
6.         if(size==0)
   
7.             return ans;
   
8.         //add nums[size-1], and count=0
   
9.         list.add(0,nums[size-1]);   
   
10.         ans.add(0,0);
    
11.         int low,high,index;
    
12.         for(int i=size-2;i>=0;i--)
    
13.         {
    
14.             low=0;high=list.size()-1;
    
15.             while(low!=high)
    
16.             {
    
17.                 int mid=(low+high)/2;
    
18.                 if(list.get(mid)<nums[i])
    
19.                     low=mid+1;
    
20.                 else
    
21.                     high=mid;
    
22.             }
    
23.             index=(list.get(low)<nums[i])?(low+1):low;
    
24.             list.add(index,nums[i]);
    
25.             ans.add(0,index);
    
26.         }
    
27.         return ans;
    
28. }

复制代码

[/i][/i][/i]

格林匹施ZELQ 发表于 2020-9-30 14:06
add在特定位置的复杂度是O(n)，你的方法还是平方的复杂度

在头加元素呢，我觉得是O(1)而不是O(n)?另一个已经知道是O(n)了，谢谢指出。
这个操作看一下ans.add(0,index);？

补充内容 (2020-10-1 00:31):
已经知道了，链表有头尾节点，所以这个操作是O（1）

补充内容 (2020-10-1 01:15):
ArrayList, 头部插入O(n);
LinkedList,头部插O(1)—&gt;addFirst()

这个是我总结的，如有不对，请大家指正。

AmberCBDP 发表于 2020-10-1 02:42
这个是我总结的，如有不对，请大家指正。

正确，但是这道题小于O（n^2）的算法是需要更复杂的数据结构才行

david_smith 发表于 2020-09-30 17:55:26
正确，但是这道题小于O（n^2）的算法是需要更复杂的数据结构才行

了解，因为想给后来的人看问题所在。从回复来看，可能也有人不太清楚问题所在，不过都很感谢大家的回复.

稍微补充一下，双向队列头尾插入删除可以O1