LeetCode [1182] Shortest Distance to Target Color

1182. Shortest Distance to Target Color

Medium

You are given an array colors, in which there are three colors: 1, 2 and 3.

You are also given some queries. Each query consists of two integers i and c, return the shortest distance between the given index i and the target color c. If there is no solution return -1.

 

Example 1:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

Example 2:

Input: colors = [1,2], queries = [[0,3]]
Output: [-1]
Explanation: There is no 3 in the array.

 

Constraints:

• 1 <= colors.length <= 5*10^4
• 1 <= colors[i] <= 3
• 1 <= queries.length <= 5*10^4
• queries[i].length == 2
• 0 <= queries[i][0] < colors.length
• 1 <= queries[i][1] <= 3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

class Solution { public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) { HashMap<Integer, List<Integer>> map = new HashMap<>(); for (int i = 0; i < colors.length; i++) { int c = colors[i]; map.putIfAbsent(c, new ArrayList<>()); map.get(c).add(i); } List<Integer> ans = new ArrayList<>(); for (int[] query : queries) { int index = query[0]; int c = query[1]; if (!map.containsKey(c)) { ans.add(-1); } else { ans.add(binarySearch(index, map.get(c))); } } return ans; } public int binarySearch(int index, List<Integer> list) { int left = 0; int right = list.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (list.get(mid) < index) { left = mid + 1; } else { right = mid; } } int res = left; if (left - 1 >= 0 && index - list.get(left - 1) < list.get(left) - index) { res = left - 1; } return Math.abs(list.get(res) - index); } }

YMSF

第二轮利口1182 要求pre compute o（n），follow up二维color矩阵，要求pre compute o（mn），之后query o（k），k为query次数

请问第二轮, 要怎么pre computer达到时间复杂度的要求?

是color number是constant吗?还是有甚么办法呢?

樓主二維的precompute是這樣做嗎?

比方說

[[1,2,1],

[2,1,1],

[1,1,1]]

生成 pre[color][x][y]

pre[2][][] initialize, 同色mark 0, O(xy):

[999,0,999],

[0,999,999],

[999,999,999]

pre[2][][]: Queue 存 (0,1) (1,0) bfs 四周 if not visited mark +1, 存到queue

[1,0,1],

[0,1,2],

[1,2,3]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { Map<Integer, TreeSet<Integer>> map = new HashMap<>(); public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) { for(int i=0; i<colors.length; ++i){ int c = colors[i]; map.computeIfAbsent(c, k->new TreeSet<>()).add(i); } List<Integer> list = new ArrayList<>(); for(int[] q : queries){ list.add(getDistance(q[0], q[1])); } return list; } int getDistance(int index, int color){ if(!map.containsKey(color)) return -1; Integer l = map.get(color).floor(index); Integer r = map.get(color).ceiling(index); int d = Integer.MAX_VALUE; if(l!=null) d = Math.min(d, Math.abs(l-index)); if(r!=null) d = Math.min(d, Math.abs(r-index)); return d==Integer.MAX_VALUE?-1:d; } }