Почему решение hashset принято, в то время как с помощью hashmap получается тайм-аут ошибки-Поиск пар в массиве с разницей K? - PullRequest
Новая
       10

Почему решение hashset принято, в то время как с помощью hashmap получается тайм-аут ошибки-Поиск пар в массиве с разницей K?

0 голосов
/ 24 ноября 2018

У меня был вопрос, где проблема заключалась в том, чтобы найти количество пар, которое имеет значение. K Ниже приведен код того же самого. В приведенном ниже коде я использовал hashmap, однако он дал правильный ответ, но для немногих изВ сценарии у меня есть тайм-аут, где при использовании HashSet все тестовые случаи были пройдены. Может кто-нибудь помочь, почему при использовании хэш-карты я получаю ошибку тайм-аута, тогда как в реальном сценарии вычисление хеш-карты происходит быстрее по сравнению с хэш-набором.

static int pairs(int k, int[] arr) {

        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<arr.length;i++)
            map.put(i,arr[i]);

        int count=0;
        for(int j=0;j<arr.length;j++)
        {
            if(map.containsValue(arr[j]-k))
            count++;
        }
        return count;
    }

Поправьте меня, если мое понимание неверно. Заранее спасибо за то же самое.

Ответы [ 2 ]

0 голосов
/ 24 ноября 2018

Поиск ключа в HashMap - это O (1) *, но поиск значения - это O (n) - он должен проходить по каждой записи, по одной за раз, до тех пор, поканаходит совпадающее значение.

Если вы хотите аналогичное поведение с HashSet, вам нужно поместить в ключи то, что вы искали, а не значения.Затем вы будете использовать containsKey, и вам никогда не будет важно, какие значения есть.В сущности, это на самом деле реализация HashSet, которую OpenJDK использует .

*, на самом деле это немного сложнее, но вы можете думать об этом как о (1) большую часть времени

0 голосов
/ 24 ноября 2018

Вероятно, вы можете написать код таким образом и проверить: - 

import java.util.*; 

class GFG { 

/* Returns count of pairs with 
difference k in arr[] of size n. */
static int countPairsWithDiffK(int arr[], int n, 
                                        int k) 
{ 
    int count = 0; 
    Arrays.sort(arr); // Sort array elements 

    int l = 0; 
    int r = 0; 
    while(r < n) 
    { 
        if(arr[r] - arr[l] == k) 
        { 
            count++; 
            l++; 
            r++; 
        } 
        else if(arr[r] - arr[l] > k) 
            l++; 
        else // arr[r] - arr[l] < sum 
            r++; 
    } 
    return count; 
} 


public static void main(String[] args) 
{ 
    int arr[] = {1, 5, 3, 4, 2}; 
    int n = arr.length; 
    int k = 3; 
    System.out.println("Count of pairs with given diff is " + 
                        countPairsWithDiffK(arr, n, k)); 
} 
}

Сложность времени : O (nlogn)

...