関小君刷题记

题目大意：

与目标颜色间的最短距离

给你一个数组 colors，里面有 1、2、 3 三种颜色。
我们需要在 colors 上进行一些查询操作 queries，其中每个待查项都由两个整数 i 和 c 组成。
現在请你帮忙设计一个算法，查找从索引 i 到具有目标顏色 c 的元素之间的最短距离。
如果不存在解決方案，请返回 -1。

示例1：

输入: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
输出: [3,0,3]
解释: 
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).

示例2：

输入: colors = [1,2], queries = [[0,3]]
输出: [-1]
解释: There is no 3 in the array.

提示：

• 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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1182

解题思路分析：

要确定某一个点距离特定颜色的距离，最简单的办法是从该点向两侧扩散去找到最短距离，但是这样做效率不高。我们可以利用前缀和的方式统计出每种颜色在[0, i]区间内出现的个数。用题目的例子来举例说明，

colors = [1,1,2,1,3,2,2,3,3]

如果统计颜色1的前缀和，结果应该是：

colorCount=[1,2,2,3,3,3,3,3,3]

数组的值变化出现在index 0，1，3，也就是说这三位是出现颜色1的地方。如果我们想查找下标2距离最近的颜色1在哪里，先看下标2所在的位置存在几个1，通过前缀和数组可知下标2所在的位置存在2个1，也就是说下标2位于第2个1与第3个1之间（如果第3个1存在的话），因此我们要找到第2个1出现的位置以及第3个1出现的位置，判断距离较短的一个即为结果。由于前缀和数组是递增（非递减）数组，因此使用二分查找该位置更加有效率。

实现代码：

public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
    int[][] colorCount = new int[4][colors.length]; // 前缀和
    colorCount[colors[0]][0]=1; // 将第一个颜色加入前缀和数组
    for(int i=1;i<colors.length;i++){ // 循环数组中每个颜色
        for(int j=1;j<=3;j++){ // 更新当前每种颜色的前缀和
            if(j==colors[i]){ // 如果i为当前颜色，
                // 当前颜色个数加一
                colorCount[j][i] = colorCount[j][i-1]+1;
            }else{
                // 如果i不是当前颜色，当前颜色个数不变
                colorCount[j][i] = colorCount[j][i-1];
            }
        }
    }
    // 返回结果
    List<Integer> res = new ArrayList<>();
    for(int[] query : queries){ // 循环每个query
        // 查看当前位置下存在多少个目标颜色
        int target = colorCount[query[1]][query[0]];
        // 距离左边目标颜色的长度
        int dis1=binarySearch(colorCount[query[1]],target,query[0]);
        // 距离右边目标颜色的长度
        int dis2=binarySearch(colorCount[query[1]],target+1,query[0]);
        // 最小距离
        int min = Math.min(dis1,dis2);
        // 如果最小距离非法，返回-1
        res.add(min==colors.length?-1:min);
    }
    return res;
}
// arr：该颜色出现个数的前缀和数组
// target：出现第target颜色所在的位置
// index：当前index
// 返回值：出现第target颜色所在的位置与当前index间的距离
int binarySearch(int[] arr, int target, int index){
    // 如果target为0或者target越界，返回一个非法值
    if(target>arr[arr.length-1] || target==0){
        return arr.length;
    }
    // 二分查找
    int left=0, right=arr.length-1;
    while(left<right){
        int mid=(left+right)/2;
        if(arr[mid]<target){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return Math.abs(left-index);
}

本题解法执行时间为51ms。

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

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

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1182-shortest-distance-to-target-color-解题思路分析/