Задача из LeetCode - Contains Duplicate II - 55 / 56 testcases passed

Question

Задача из LeetCode - Contains Duplicate II - 55 / 56 testcases passed

Аркадий Саакян Ученик (162), на голосовании 1 год назад

https://leetcode.com/problems/contains-duplicate-ii
Текст:
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Примеры:
Input: nums = [1,2,3,1], k = 3
Output: true
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Мой код проходит все тесты кроме последней. Никаких превышений лимита времени: просто неправильный ответ.

 class Solution { 
    
    // 100% РАБОТАЕТ ПРАВИЛЬНО
    public int binarySearch(int[] nums, int target, int left, int right) { 
        if (left > right) 
            return -1; 
        int mid = left + (right - left) / 2; 
        if (nums[mid] == target) 
            return mid; 
        if (target < nums[mid]) 
            return binarySearch(nums, target, left, mid - 1); 
        else 
            return binarySearch(nums, target, mid + 1, right); 
    } 
 
    public boolean containsNearbyDuplicate(int[] nums, int k) { 
        for (int i = 0; i < nums.length; i++) { 
            int secondIndex = binarySearch(nums, nums[i], i + 1, nums.length - 1); 
            if (secondIndex == -1) 
                secondIndex = binarySearch(nums, nums[i], 0, i - 1); 
            if (secondIndex != -1 && Math.abs(i - secondIndex) <= k) 
                return true; 
        } 
        return false; 
    } 
}

Answer 1

Проблема с вашим кодом заключается в том, что он предполагает, что входной массив nums отсортирован, что не обязательно является правдой. Алгоритм двоичного поиска работает только на отсортированных массивах, поэтому он не всегда будет возвращать правильный результат при применении к неотсортированному массиву.

Более эффективным и правильным решением этой проблемы было бы использование хеш-таблицы для отслеживания индексов элементов в массиве. Вот пример реализации на Java:

 public boolean containsNearbyDuplicate(int[] nums, int k) { 
    Map map = new HashMap<>(); 
    for (int i = 0; i < nums.length; i++) { 
        if (map.containsKey(nums[i])) { 
            if (i - map.get(nums[i]) <= k) { 
                return true; 
            } 
        } 
        map.put(nums[i], i); 
    } 
    return false; 
}

Это решение имеет временную сложность O(n), где n - длина входного массива nums. Оно использует хеш-таблицу для отслеживания самого последнего индекса каждого элемента в массиве. Для каждого элемента nums[i] он проверяет, есть ли предыдущее вхождение того же элемента на расстоянии k, ища его индекс в хеш-таблице. Если такое вхождение найдено, он возвращает true. В противном случае он обновляет индекс элемента в хеш-таблице и переходит к следующему элементу.