java несортированный массив проверяет, содержит ли он дубликаты с помощью binarySearch - PullRequest
Новая
       36

java несортированный массив проверяет, содержит ли он дубликаты с помощью binarySearch

0 голосов
/ 21 апреля 2020

При решении приведенной ниже задачи Проблема Leetcode: содержит-дубликат-ii

Учитывая массив целых чисел и целое число k, выяснить, есть ли два различных индекса i и j в массиве так, что nums [i] = nums [j], а абсолютная разница между i и j не превышает k.

После отправки решения я искал оптимизации, когда смотрел на представленный код. Двое из них я не мог понять. Они приведены ниже:

Решение 1: 

public boolean containsNearbyDuplicate(int[] nums, int k) {
        int len = nums.length;

        for(int i=0; i<len; i++) {
            int j = Arrays.binarySearch(nums, nums[i]);
            if(i != j && Math.abs(i-j) <= k) {
                return true;
            }
        }

        return false;
    }

Поскольку массив не отсортирован, как на нем работает binarySearch?

Решение 2: 

public boolean containsNearbyDuplicate(int[] nums, int k) {
         if(nums.length==0) return false;
         if(nums.length>5000) return false;


        for(int i=0;i<nums.length;i++){
        for(int j=0;j<nums.length;j++){
         if(i!=j){
            if(nums[i]==nums[j]){

            if(Math.abs(i-j)<=k)
            return true;}


        } }}

        return false;      
    }

Что означает вторая строка, т.е. если (nums.length> 5000) возвращает false; жадный? Какое отношение это имеет к длине 5000+? Очень странно. Это лучшее решение, так как оно занимает 0 мс. Но на самом деле это O (n2) в худшем случае. Таким образом, в основном это кажется производительным, потому что он возвращает рано на его размер, то есть 5000+, иначе он должен работать на самом деле плохо. По крайней мере, второй l oop должен был начаться с i + 1 до конца массива или i + k, в зависимости от того, что меньше.

...