La meilleure façon de trouver le nombre de paires dans un tableau dont la différence est k

J'ai pu résoudre le problème sur hackerrank. J'ai eu deux approches dans mon esprit :

d'entrée : tableau non trié(a) et k

Première Approche :

1) Trier le tableau

2) pour chaque élément du tableau a[i] ,trouver l'élément a[i]+K à l'aide de la recherche binaire.Si trouvé increament le comte et la rupture de la boucle interne.

Deuxième Approche :

1) Trier le tableau

2) pour chaque élément du tableau a[i] ,trouver l'élément a[i]+K à l'aide de linearsearch.Si trouvé increament le comte et la rupture de la boucle interne.

J'ai trouvé la Première approche pour être mieux comme ça permettra de résoudre le problème à n(logn). Mais lorsque plusieurs cas de test sont sur les solutions de l'approche 2 prend moins de temps . Peut quelqu'un me dire pourquoi ?

Ci-dessous sont le code pour les deux approches :

Première Approche De Code :

static int pairs(int[] a,int k) {
  /* Complete this function */
    int temp;
    int len=a.length;
    int count=0;
    int beg;
    int mid;
    int end;
    int midVal;
    Arrays.sort(a);
    for(int i=0;i<len-1;i++){
    temp=a[i]+k;
    beg=i+1;  
    end=len-1;
        for(int l=beg;l<len;l++){
            mid=(beg+end)/2;
            midVal=a[mid];
            if(midVal==temp){
                count++;
                break;
            }
            else if(midVal>temp){
                end=mid-1;
            }
            else{
                beg=mid+1;
            }
        }

    }
    return count;
}

Deuxième Code D'Approche :

static int pairs(int[] a,int k) {
  /* Complete this function */
    int temp;
    int len=a.length;
    int count=0;
    Arrays.sort(a);
    for(int i=0;i<len;i++){
    temp=a[i];
        for(int j=i+1;j<len;j++){
            if(temp-a[j]==-k){
                count++;
                break;
            }
        }
    }
    return count;
}
Dupliquer: Voici la meilleure approche stackoverflow.com/questions/4720271/...

OriginalL'auteur Sahil Gupta | 2013-11-24

  1. 6

    La première approche est le meilleur entre les deux, mais il est la meilleure approche à la fois:-

    Voici un pseudo-code pour une meilleure approche:-

    for(i=0;i<Arr.length;i++) {
  Hashmap.add(Arr[i])
}
count=0;
for(j=0;j<Arr.length;j++) {

  if(Hashmap.containsKey(Arr[j]+k))
     count++;

}

    Temps de la complexité: O(N)
    alors que votre approche = O(NlogN)

    Edit:-

    Remarque:- Mon approche a un espace supplémentaire de complexité de O(N) pour la table de Hachage considérant que l'approche suggérée est en place.

    C'est une bonne approche. Vous devez également mentionner que c'est une meilleure approche si la mémoire n'est pas un problème car il nécessairement nécessiterait O (n) de l'espace supplémentaire, tandis que les autres solutions peuvent être mises en place.
    U est bonne je fais toujours de l'espace de l'analyse de la complexité, mais a manqué cette fois. Vérifier mon montage.
    Semble bon 🙂 +1
    Il n'y a pas de add() dans la table de hachage
    Oui c'est pourquoi j'ai précisé c'est un pseudo-code.

    OriginalL'auteur Vikram Bhat

  2. 0

    Dans votre 1er code, votre intérieur de la boucle de résiliation condition est incorrect. Il devrait y mettre fin si la beg et end pointeurs de la croix les uns des autres.

    Changer de while (beg <= end) ou for (; beg <= end; )

    Aussi, pour la seconde approche, il n'est pas nécessaire pour le tri du tableau.

    Dans le second cas, si le tri n'est pas réellement de l'aide dans la réduction de l'ordre de l'algorithme, mais il pourrait aider à réduire une surcharge importante dans l'analyse linéaire si la valeur de k est petit. Bien sûr pire des cas, à la fois d'effectuer la même.
    par votre logique qu'arriverait-il si la différence est grande?
    Dans le cas où je n'utilise pas le tri pour l'approche 2 .Ensuite, j'ai besoin de chercher temp-a[j]==-k et temp-a[j]==k , donc pour cela plus ou moins le temps de complexité O(n^2). Alors que si j'trier le tableau d'abord le temps d'exécution pour plusieurs cas de test sont moins.
    si vous êtes à la réalisation d'un linéaire de recherche, puis le temps de la complexité de chaque cas de test est O (n^2) si le tableau est trié.
    Grâce abhishek pour les réponses 🙂

    OriginalL'auteur Abhishek Bansal

  3. 0

    Vous pouvez également utiliser set pas besoin d'utiliser la table de hachage 

    public static void main(String[] args) throws Exception {

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    int[] firstLine = Stream.of(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    int count = firstLine[0];
    int diff = firstLine[1];           
    Set<Integer> numbers = new HashSet<Integer>(Stream.of(in.readLine().split(" ")).map(Integer::valueOf).collect(Collectors.toList()));

    int pairCount = 0;
    for (Integer number : numbers) {
        pairCount += (numbers.contains(number+diff) ? 1:0); 
    }
    System.out.println(pairCount);                
}

    OriginalL'auteur fatih tekin

  4. 0
    private static int CountDistinctPairs(int[] nums, int k) {
    //TODO Auto-generated method stub
    HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
    HashSet<String> set = new HashSet<String>();
    for(int i =0;i < nums.length;i++){
        map.put(nums[i],true);
    }
    for (int i = 0 ; i < nums.length; i++){
        if(map.containsKey(nums[i]+k)){
            String a = "";
            if(nums[i]<nums[i]+k){
                a = "("+nums[i]+","+(nums[i]+k)+")";
            }
            else{
                a = "("+(nums[i] + k)+","+nums[i]+")";
            }
            set.add(a);
        }
    }
    System.out.println(set);
    return set.size();
}

    OriginalL'auteur Saif ali Karedia

  5. 0
    static boolean checkDuplicatesWithinK(int arr[], int k)
    {
        //Creates an empty hashset
        HashSet<Integer> set = new HashSet<>();

        //Traverse the input array
        for (int i=0; i<arr.length; i++)
        {
            //If already present n hash, then we found 
            //a duplicate within k distance
            if (set.contains(arr[i]))
               return true;

            //Add this item to hashset
            set.add(arr[i]);

            //Remove the k+1 distant item
            if (i >= k)
              set.remove(arr[i-k]);
        }
        return false;
    }

public static void main (String[] args)
    {
        int arr[] = {10, 5, 3, 4, 3, 5, 6};
        if (checkDuplicatesWithinK(arr, 3))
           System.out.println("Yes");
        else
           System.out.println("No");
    }
    pourriez-vous ajouter quelques explications à ce code? pour améliorer votre réponse et pour aider les futurs lecteurs

    OriginalL'auteur Deepak Maddeshiya

  6. 0

    Ma solution

    Système..println("findPair:"+findPair(new int[]{4,7,1,2,5,3,0,7,8,5,2}, 3));

    public static int findPair(int[] nums, int target){ 
    Arrays.sort(nums);

    int count = 0;
    String pairText = "";
    for(int i =0; i < nums.length;i++){
        for(int j =i+1; j < nums.length;j++){

            if(nums[j]-nums[i] == target && (!pairText.equals(nums[i]+", "+nums[j]))){

                //System.out.println(nums[i]+", "+nums[j]);
                pairText = nums[i]+", "+nums[j];
                count++;
            }
        }

    }  


    return count;


}

    OriginalL'auteur Wei-Hsuan Chou