Bir massivdə dublikatları ən səmərəli şəkildə tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Bloomberg Facebook google lyft microsoft Paytm Cib daşları Qualcomm Zoho
GeyimBaxılıb 343

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Təkrarlanan bütün elementləri O (n) və O (1) boşluğunda ən səmərəli şəkildə göstərin. Verilmişdir array 0-dan n-1 aralığındakı rəqəmləri ehtiva edən n ölçüsündə bu rəqəmlər istənilən dəfə baş verə bilər. Bir seriyada dublikatları ən səmərəli şəkildə tapın. Yəni rəqəm artıq massivdə meydana gəlmişsə, rəqəm təkrarlanır.

misal

Input

23

1 5 4 2 8 4 1 0 0 2 4 9 4 2 4 6 6 7 3 1 0 0 0 XNUMX

Buraxılış

4 1 0 2 4 4 2 4 6 1 0 0 0

Bir massivdə dublikatları ən səmərəli şəkildə tapmaq üçün yanaşma

İndi anlayırıq problemi anlayırıq. Beləliklə, çox vaxt almadan birbaşa problemin həyata keçirilməsi üçün istifadə olunan alqoritmə keçirik.

Alqoritm

1. Sıfırın təkrarlanması üçün ayrıca bir dəyişən götürün.
2. Sonra, serialı keçin.
3. Element sıfırsa, artım sıfırdır. Əgər say 1-dən böyükdürsə, onu təkrarlandıqca göstərin.
4. Əgər sıfırdan başqa bir şey varsa, durduğunuz elementin mütləq dəyəri ilə göstərilən massivin indeksinə, yəni arr [abs (arr [i])] -ə gedin və müsbətdirsə, onu mənfi göstərin indeks olan element bir dəfə meydana gəldi.
5. Əgər bir dublikat alsaq, arr [abs (arr [i])] - nin artıq əks işarəli olduğunu görərik və onu sadəcə çap edə bilərik.

Həyata keçirilməsi

Bir serialda dublikatları ən səmərəli şəkildə tapmaq üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
      cin>>arr[i];
    }
    int zero = 0; //separate case for zero
    for(int i = 0; i < N; i++)
    {
    if(arr[i] == 0)
      {
        if(zero > 0)
          cout << 0 << " ";
        
        zero++;
      }
      
    else if(arr[abs(arr[i])] >= 0)  // we take the element's value as the index and change the sign of the element at that position
    arr[abs(arr[i])] = - arr[abs(arr[i])];
    
    else    //if we have duplicates then we will encounter a location whose value is negative
     cout << abs(arr[i]) <<" ";
   }
   return 0;
}

Bir Arrayda Dublikatları Ən Səmərəli Bir şəkildə Tapmaq üçün Java Proqramı

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            return -1*x;
        }
        else
        {
            return x;
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int zero = 0; //separate case for zero
        for(int i = 0; i < n; i++)
        {
        if(a[i] == 0)
          {
            if(zero > 0)
              System.out.print(0+" ");
            zero++;
          }
        else if(a[abs(a[i])] >= 0)  // we take the element's value as the index and change the sign of the element at that position
        a[abs(a[i])] = - a[abs(a[i])];
        else    //if we have duplicates then we will encounter a location whose value is negative
         System.out.print(abs(a[i])+" ");
       }
    }
}
23
1 5 4 2 8 4 1 0 0 2 4 9 4 2 4 6 6 7 3 1 0 0 0
4 1 0 2 4 4 2 4 6 1 0 0 0

Bir massivdə dublikatları ən səmərəli şəkildə tapmaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (N) burada N - verilən massivdə mövcud olan elementlərin sayıdır, burada bütün massivi keçib cavabımızı hesablayırıq.

Kosmik Mürəkkəblik

O (1) çünki nəticələrin hesablanmasında köməkçi yerdən istifadə etməyəcəyik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »