和脸八字不合面经 店面 + 昂塞

billyRandom 发表于 2021-2-17 22:12
Count unique elements in sorted array 这题什么解法的time complexity会小于O(N)? 至少需要扫描一遍数组 ...

对于每个数字，用binary search找最右边相等的元素：
https://leetcode.com/discuss/int ... nic-london-may-2020

请问下是system design还是product design?

Jennifer1986 发表于 2021-02-19 13:08:39
请问下是system design还是product design?

system design

电面考 巴而期 楼主怎么做的，UF 可以做但是似乎很慢，暂时想不到比UF更快的办法

Byleth 发表于 2021-02-21 11:32:08
电面考 巴而期 楼主怎么做的，UF 可以做但是似乎很慢，暂时想不到比UF更快的办法

我用的dp ，跟利口上的答案差不多思路

billyRandom 发表于 2021-2-18 14:12
Count unique elements in sorted array 这题什么解法的time complexity会小于O(N)? 至少需要扫描一遍数组 ...

回头把bisect自己实现一下就好了吧

1. import bisect
   
2. def count_unique_in_sorted(array):
   
3.     res = 1
   
4.     start = array[0]
   
5. 
   
6.     idx = bisect.bisect_right(array,start)
   
7.     while idx < len(array):
   
8.         res += 1
   
9.         start = array[idx]
   
10.         idx = bisect.bisect_right(array,start)
    
11.     return res
    

复制代码

Byleth 发表于 2021-2-22 11:11
回头把bisect自己实现一下就好了吧[mw_shl_code=bash,true]import bisect
def count_unique_in_sorted(a ...

谢谢！

"3. A. Count unique elements in sorted array, 要求当有很多重复数字的时候，time complexity小于O(N)"

这题是个好题目，写一个

1. int count_uniq(vector<int> &nums)
   
2. {
   
3.     int n = nums.size();
   
4. 
   
5.     /*  
   
6.      0 1 2 3 4 5 6 7 8 9 10
   
7.      ---------------------
   
8.      3,6,6,6,6,6,6,7,7,8,9
   
9.     */
   
10. 
    
11.     int ans = 0;
    
12.     int i = 0;
    
13. 
    
14.     while (i < n) {
    
15.         auto it = upper_bound(nums.begin(), nums.end(), nums[i]);
    
16.         i = it - nums.begin();
    
17.         ans++;
    
18.     }   
    
19. 
    
20.     return ans;
    
21. }

复制代码