1182. Shortest Distance to Target Color

Version #2 Binary search on index list[TODO] - worse time complexity

二刷 07/2022

Version #1 Scan from two ends

感觉写的比上次简洁一点

方法是一样的

Time O(N + Q) - N is the length of colors, Q is the length of the queries

Space O(N)

Runtime: 30 ms, faster than 79.06% of Java online submissions for Shortest Distance to Target Color.

Memory Usage: 131.1 MB, less than 20.94% of Java online submissions for Shortest Distance to Target Color.

class Solution {

    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {

        int[][] dist = new int[colors.length][3];

        int[] index = new int[3];

        Arrays.fill(index, -1);

        for (int i = colors.length - 1; i >= 0; i--) {

            Arrays.fill(dist[i], Integer.MAX_VALUE);

            updateDist(i, colors, dist, index);

        }

        Arrays.fill(index, -1);

        for (int i = 0; i < colors.length; i++) {

            updateDist(i, colors, dist, index);

        }

        List<Integer> result = new ArrayList<>();

        for (int[] query : queries) {

            int d = dist[query[0]][query[1] - 1];

            result.add(d == Integer.MAX_VALUE ? -1 : d);

        }

        return result;

    }

    

    private void updateDist(int i, int[] color, int[][] dist, int[] index) {

        index[color[i] - 1] = i;

        for (int c = 0; c < 3; c++) {

            if (index[c] == -1) {

                continue;

            }

            dist[i][c] = Math.min(dist[i][c], Math.abs(index[c] - i));

        }

    }

}

一刷 07/2022

Version #1 Scan from two ends

Time O(N + Q) - N is length of colors, Q is length of the queries

Space O(N)

Runtime: 38 ms, faster than 71.82% of Java online submissions for Shortest Distance to Target Color.

Memory Usage: 126.6 MB, less than 40.68% of Java online submissions for Shortest Distance to Target Color.

 class Solution {

    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {

        int[][] dist = new int[colors.length][3];

        int[] pointers = new int[]{-1, -1, -1};

        for (int i = 0; i < colors.length; i++) {

            Arrays.fill(dist[i], Integer.MAX_VALUE);

            updatePointers(colors, i, pointers);

            updateDist(dist, i, pointers);

        }

        for (int i = colors.length - 1; i >= 0; i--) {

            updatePointers(colors, i, pointers);

            updateDist(dist, i, pointers);

        }

        List<Integer> result = new ArrayList<>();

        for (int[] query : queries) {

            int d = dist[query[0]][query[1] - 1];

            result.add(d == Integer.MAX_VALUE ? -1 : d);

        }

        return result;

    }

    

    private void updateDist(int[][] dist, int index, int[] pointers) {

        for (int i = 0; i < 3; i++) {

            if (pointers[i] == -1) {

                continue;

            }

            int d = Math.abs(index - pointers[i]);

            if (d < dist[index][i]) {

                dist[index][i] = d;

            }

        }

    }

    

    private void updatePointers(int[] colors, int i, int[] pointers) {

        switch (colors[i]) {

            case 1: pointers[0] = i;

                break;

            case 2: pointers[1] = i;

                break;

            case 3: pointers[2] = i;

                break;

        }

    }

}