Java binary search solution


  • 0
    M
    class Node {
        int id;
        String timestamp;
        
        public Node(int i, String t) {
            id = i;
            timestamp = t;
        }
    }
    
    public class LogSystem {
       
        List<Node> list = new ArrayList<>();
        List<String> units = Arrays.asList("Year", "Month", "Day", "Hour", "Minute", "Second");
        int[] indices = new int[]{4, 7, 10, 13, 16, 19};
    
        public LogSystem() {
        }
        
        public void put(int id, String timestamp) {
            int idx = binarySearch(timestamp, 19);
            list.add(idx, new Node(id, timestamp));
        }
        
        public List<Integer> retrieve(String s, String e, String gra) {
            List<Integer> res = new ArrayList<>();
            int idx = indices[units.indexOf(gra)];
            int start = binarySearch(s, idx);
            while (start < list.size() && compare(list.get(start).timestamp, e, idx) <= 0) {
                res.add(list.get(start).id);
                start++;
            }
            return res;
        }
        
        public int binarySearch(String ts, int idx) {
            if (list.size() == 0)
                return 0;
            int low = 0, high = list.size() - 1;
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (compare(list.get(mid).timestamp, ts, idx) < 0)
                    low = mid + 1;
                else
                    high = mid;
            }
            return compare(list.get(low).timestamp, ts, idx) < 0? low + 1: low;
        }
        
        public int compare(String ts1, String ts2, int idx) {
            return ts1.substring(0, idx).compareTo(ts2.substring(0, idx));
        }
        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.