3488. Closest Equal Element Queries - Medium

前往題目

想法

• 紀錄所有數字的index
• 根據query計算每個數字距離鄰居的最短距離

思路

寫完先瘋一半，要一直切換數字與index，腦袋快炸掉，這是這週周賽的第二題

1. 紀錄所有數字的index
2. 找出當前query的index在query的實際數字的index list中的位置(這樣才能更快判斷鄰居，因為index list中鄰居都是相同數字，只紀錄index)
3. 每個query數字計算其左邊鄰居，與右邊circular情況下的鄰居
4. 最後輸出結果

我覺得最難的大概就是index和數字之間切換會很容易出錯😢

Code

網友解答

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        // Number -> index list
        Map<Integer, ArrayList<Integer>> indexMap = new HashMap();
        // Record the number and its all appearance index
        for (int i = 0; i < nums.length; ++i) {
            // Check if the number already exists
            if (!indexMap.containsKey(nums[i])) {
                indexMap.put(nums[i], new ArrayList<>());
            }
            indexMap.get(nums[i]).add(i); // Add the index of the number
        }

        ArrayList<Integer> res = new ArrayList();

        // Iterate through all the queries and cal. the minimum range
        for (int query : queries) {
            res.add(solve(indexMap.get(nums[query]), query, nums.length));
        }
        return res;
    }

    private int solve(ArrayList<Integer> list, int query, int size) {
        if (list == null || list.size() < 2) return -1;
        int pos = binarySearch(list, query); // Search for the index position of the current query in the index list
        // If first one, neighbor is the last element; if not, previous one        
        int leftNeighbor = pos == 0 ? list.get(list.size() - 1) : list.get(pos - 1);
        // If last one, neighbor is the first element; if not, next one
        int rightNeighbor = pos == list.size() - 1 ? list.get(0) : list.get(pos + 1);

        return Math.min(dist(query, leftNeighbor, size), dist(query, rightNeighbor, size));
    }

    private int dist(int query, int neighbor, int size) {
        int dist = Math.abs(query - neighbor);
        return Math.min(dist, size - dist);
    }

    private int binarySearch(ArrayList<Integer> list, int query) {
        int l = 0, r = list.size() - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            // Found the index of the number
            if (list.get(mid) == query) {
                return mid;
            } else if (list.get(mid) < query) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return l;
    }
}

▶

WA

沒考慮circular的情況

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        // Num -> its distribution
        Map<Integer, boolean[]> map = new HashMap();

        // Record the position of each num
        for (int i = 0; i < nums.length; ++i) {
            // The number already exists
            if (map.containsKey(nums[i])) {
                // Mark the number at the index
                map.get(nums[i])[i] = true;
            } else { // The number doesn't exist
                // Init the position indication array
                map.put(nums[i], new boolean[nums.length]);
                // Put the current number inside
                map.get(nums[i])[i] = true;
            }
        }

        List<Integer> res = new ArrayList();

        // Iterating the queries
        for (int index : queries) {
            int searchNum = nums[index];
            
            boolean[] checkArr = map.get(searchNum);
            int closestRange = Integer.MAX_VALUE;
            int firstOccurIndex = -1;
            
            for (int i = 0; i < checkArr.length; ++i) {
                if (firstOccurIndex == -1) firstOccurIndex = i;
                
                if (!checkArr[i] || i == index) continue;
                
                closestRange = Math.min(closestRange, Math.abs(index - i));
                // Check circular condition
                if (firstOccurIndex != -1) {
                    closestRange = Math.min(closestRange, checkArr.length % (index + 1) + firstOccurIndex + 1 + 1);
                }
                    
            }

            // Not found
            if (closestRange == Integer.MAX_VALUE) {
                res.add(-1);
            } else { // Found
                res.add(closestRange);
            }
        }

        return res;
    }
}