Count the number of Vector - FB prepare

http://www.cnblogs.com/EdwardLiu/p/6399857.html

给一个超级大的排好序的vector  [abbcccdddeeee]比如，要求返回[{1,a}, {2,b}, {3,c}, {4,d}, {5,e}......]复杂度要优于O(N)

分析：

如果是binary search找每个char的上下界，worst case要找n次，时间复杂度O(nlogn)

所以考虑每次比较start point和start point + 2^n位置上的数，假如一样就continue，不一样就在区间里面binary search找上界，这样worst case O（N）

 7     public List<List<Character>> reorganize(String str) {
 8         List<List<Character>> res = new ArrayList<List<Character>>();
 9         if (str==null || str.length()==0) return res;
10         int starter = 0;
11         int n = 0;
12         while (starter < str.length()) {
13             char cur = str.charAt(starter);
14             int index = starter + (int)Math.pow(2, n);
15             while (index < str.length() && str.charAt(index) == cur) {
16                 n++;
17                 index = starter + (int)Math.pow(2, n);
18             }
19             if (index >= str.length()) 
20                 index = str.length() - 1;
21             int rightEdge = findRight(str, starter, index, cur);
22             List<Character> newItem = new ArrayList<Character>();
23             newItem.add((char)('0'+ rightEdge-starter+1));
24             newItem.add(cur);
25             res.add(newItem);
26             
27             starter = rightEdge + 1;
28             n = 0;
29         }
30         return res;
31     }
32     
33     public int findRight(String str, int starter, int end, char target) {
34         int l = starter;
35         int r = end;
36         while (l <= r) {
37             int m = (l + r)/2;
38             if (str.charAt(m) == target)
39                 l = m + 1;
40             else r = m - 1;
41         }
42         return r;
43     }