FB面经prepare: Count the number of Vector

给一个超级大的排好序的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）

package fb;

import java.util.*;

public class ReorganizeVector {
    
    public List<List<Character>> reorganize(String str) {
        List<List<Character>> res = new ArrayList<List<Character>>();
        if (str==null || str.length()==0) return res;
        int starter = 0;
        int n = 0;
        while (starter < str.length()) {
            char cur = str.charAt(starter);
            int index = starter + (int)Math.pow(2, n);
            while (index < str.length() && str.charAt(index) == cur) {
                n++;
                index = starter + (int)Math.pow(2, n);
            }
            if (index >= str.length()) 
                index = str.length() - 1;
            int rightEdge = findRight(str, starter, index, cur);
            List<Character> newItem = new ArrayList<Character>();
            newItem.add((char)('0'+ rightEdge-starter+1));
            newItem.add(cur);
            res.add(newItem);
            
            starter = rightEdge + 1;
            n = 0;
        }
        return res;
    }
    
    public int findRight(String str, int starter, int end, char target) {
        int l = starter;
        int r = end;
        while (l <= r) {
            int m = (l + r)/2;
            if (str.charAt(m) == target)
                l = m + 1;
            else r = m - 1;
        }
        return r;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ReorganizeVector sol = new ReorganizeVector();
        List<List<Character>> res = sol.reorganize("abbcccddddeeeee");
        for (List<Character> line : res) {
            for (Character c : line) System.out.print(c);
            System.out.println("");
        }
    }

}