文章目录
- 1、题目描述
- 2、解题思路
- 3、解题代码
1、题目描述
2、解题思路
??题意：找出特定颜色中最靠近指定位置的那一个，并且求出这个距离。
??对于 queries = [[1,3],[2,2],[6,1]]，其中[1,3] 的 1 表示指定位置，3 表示特定颜色，即在 colors 中颜色为 3 的所有索引中，找到最靠近位置 1 的那个，并求出这个最短距离。
??把三种颜色在 colors 中的索引位置分别标记出来，比如：colors = [1,1,2,1,3,2,2,3,3]
??那么三种颜色索引数组为：
??int[] one = {0,1,3}
??int[] two = {2,5,6}
??int[] three = {4,7,8}
??于是问题就转化为：从数组（one\two\three 三者其一）中找到最靠近目标值 key 的元素，并求出这个元素和 key 的差值绝对值。
??选择哪个数组就看 queries[i][1]，目标值 key 就是queries[0][1]
??接下来就是遍历 queries
??1、对于遍历到的queries[i]，从 queries[i][1] 判断待搜索数组是 one、two 还是 three；
??2、使用二分法，从数组中找是否存在 queries[i][0] 的值；
??3、如果数组中存在 queries[i][0] ，说明此时的距离为 0；
??4、如果数组中不存在 queries[i][0]，则有三种情况：
??4.1 queries[i][0] 比数组最小值还小，那么此时最短距离就是 queries[i][0] 和最小值的差的绝对值；
??4.2 queries[i][0] 比数组最大值还大，那么此时最短距离就是 queries[i][0] 和最大值的差的绝对值；
??4.3 queries[i][0] 比最小值大，比最大值小。那么，queries[i][0] 肯定在某个索引 idx 和 idx+1 的值之间，我们计算 queries[i][0] 和第 idx 位元素差值绝对值，再计算 queries[i][0] 和 idx+1 位元素差的绝对值，最小的那个就是最小距离。
3、解题代码
class Solution {
public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
List<Integer> ans = new ArrayList<>();if (queries.length == 0) {
return ans;}Map<Integer, List<Integer>> map = new HashMap<>();map.put(1, new ArrayList<>());map.put(2, new ArrayList<>());map.put(3, new ArrayList<>());for (int i = 0; i < colors.length; i++) {
map.get(colors[i]).add(i);}for (int[] query : queries) {
List<Integer> ls = map.get(query[1]); // 数组 ls 保存的是 query[1] 颜色在 colors 中的所有位置索引if (ls.size() == 0) {
// 不存在这个颜色ans.add(-1);continue;}// 在 ls 中有没有 query[0] 这个值int index = Collections.binarySearch(ls, query[0]);if (index >= 0) {
// ls 中存在 key// 既然 ls 中存在 key，说明 key 和 ls 中差值最小的就是 0ans.add(0);} else {
// list 不存在 key，此时 index 为：-insertPoint-1// insertPoint 表示 ls 中，比 key 大的最小值的索引int insertPoint = -index - 1; // index = - insertPoint - 1;if (insertPoint == ls.size()) {
// 说明 key 比 ls 中最大值还大，那么 ls 中和 key 的最小差值就是 key 和最大的那个之差ans.add(query[0] - ls.get(insertPoint - 1));} else if (insertPoint == 0) {
// 说明 key 比 ls 中最小值还小，那么 ls 中和 key 的最小差值就是最小元素 - keyans.add(ls.get(0) - query[0]);} else {
// 说明 key 比 ls 中最小值大，比最大值小ans.add(Math.min(ls.get(insertPoint) - query[0], query[0] - ls.get(insertPoint - 1)));}}// if (index >= 0) { // ls 中有这个值，说明 query[1] 颜色和 colors[query[0]] 是同一个颜色
// ans.add(0);
// } else if (index == -1) { // ls 中所有值都比 query[0] 小
// ans.add(ls.get(0) - query[0]);
// } else if (index == -(ls.size() + 1)) { // 没有 key，inde 为 -insertPoint-1
// ans.add(query[0] - ls.get(ls.size() - 1));
// } else {
// int location = -index - 1;
// ans.add(Math.min(query[0] - ls.get(location - 1), ls.get(location) - query[0]));
// }}return ans;}
}