心塞的fb电面跪经

第二题不是 count and say 吗？

补充内容 (2017-2-5 03:08):
记错了..并不是

LeoJY 发表于 2017-2-5 02:49
二分的话最差应该nlgn吧？ 假如所有数字都不一样，找上界下界都是lgn，然后要找n次。。。

所有数字都不一样的 那就是O1 的时间吗？
最坏还是On 吧

二分最差是nlogN但是第二个N最差情况时是2，所以最后还是n

zhhan1990 发表于 2017-2-4 15:21
二分最差是nlogN但是第二个N最差情况时是2，所以最后还是n

大n为啥最差是2啊……没理解你的意思……

感谢楼主分享。按照楼主的思路，第二题是不是这样做的？

1. class Solution {
   
2. public:
   
3.     vector<pair<int, int>> countNums(vector<int> &nums) {
   
4.         vector<pair<int, int>> res;
   
5.         int st = 0;
   
6.         while (st < (int)nums.size()) {
   
7.             int ed = findLastOf(nums, st, nums[st]);
   
8.             res.push_back( {nums[st], ed - st + 1} );
   
9.             st = ed + 1;
   
10.         }
    
11.         return res;
    
12.     }
    
13. 
    
14. private:
    
15.     int findLastOf(const vector<int> &nums, int st, int target) {
    
16.         int left = st;
    
17.         int diff = 1;
    
18.         while (left + diff < (int)nums.size()) {
    
19.             if (nums[left + diff] <= target) {
    
20.                 left += diff;
    
21.                 diff *= 2;
    
22.             } else {
    
23.                 break;
    
24.             }
    
25.         }
    
26. 
    
27.         int right = min((int)nums.size() - 1, left + diff);
    
28.         return binarySearch(nums, left, right, target);
    
29.     }
    
30. 
    
31.     int binarySearch(const vector<int> &nums, int left, int right, int target) {
    
32.         while (left + 1 < right) {
    
33.             int mid = left + (right - left) / 2;
    
34.             if (nums[mid] <= target) {
    
35.                 left = mid;
    
36.             } else {
    
37.                 right = mid;
    
38.             }
    
39.         }
    
40. 
    
41.         if (nums[right] == target)
    
42.             return right;
    
43.         return left;
    
44.     }
    
45. };
    

复制代码

觉得楼主想法还是挺精妙的, 不过我觉得这个题目没啥意思, 因为直接一遍读过去一样就是average case O(n)..

lhh_NJU 发表于 2017-2-19 02:53
觉得楼主想法还是挺精妙的, 不过我觉得这个题目没啥意思, 因为直接一遍读过去一样就是average case O(n)..

现在是worst case on呀

第二题

1. public class DecodeVector {
   
2. 
   
3.     class Pair {
   
4.         int c;
   
5.         int count;
   
6.         public Pair(int c, int count) {
   
7.             this.c = c;
   
8.             this.count = count;
   
9.         }
   
10.     }
    
11. 
    
12.     public List<Pair> getCount(int[] arr) {
    
13.         List<Pair> list = new ArrayList<>();
    
14.         if (arr == null || arr.length == 0) {
    
15.             return list;
    
16.         }
    
17. 
    
18.         int start = 0;
    
19.         while (start < arr.length) {
    
20.             int end = findLast(start, arr);
    
21.             list.add(new Pair(arr[start], end - start + 1));
    
22.             start = end + 1;
    
23.         }
    
24. 
    
25.         return list;
    
26.     }
    
27. 
    
28.     private int findLast(int start, int[] arr) {
    
29.         int c = arr[start];
    
30.         int diff = 1;
    
31.         while (start + diff < arr.length && arr[start + diff] == c) {
    
32.             diff <<= 1;
    
33.         }
    
34.         if (start + diff >= arr.length) {
    
35.             return arr.length - 1;
    
36.         }
    
37. 
    
38.         int end = start + diff;
    
39.         while (start + 1 < end) {
    
40.             int mid = (end - start) / 2 + start;
    
41.             if (arr[mid] == c) {
    
42.                 start = mid;
    
43.             } else {
    
44.                 end = mid;
    
45.             }
    
46.         }
    
47.         if (arr[end] == c) {
    
48.             return end;
    
49.         } else {
    
50.             return start;
    
51.         }
    
52.     }
    
53. 
    
54. 
    
55.     public static void main(String[] args) {
    
56.         int[] arr = {1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3};
    
57.         DecodeVector d = new DecodeVector();
    
58.         List<Pair> res = d.getCount(arr);
    
59.         for (Pair p : res) {
    
60.             System.out.println(p.c + ": " + p.count);
    
61.         }
    
62.     }
    
63. }
    

复制代码

这个 worse case 负责度是 O(NlgN) 吧

恭喜楼主onsite 你约了哪一天了吗