صف میں زیادہ سے زیادہ دہرانے والا نمبر تلاش کریں  


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل بلومبرگ درگ ای بے فیس بک گولڈمین سیکس گوگل Intuit مائیکروسافٹ نیوٹنکس پے پال Salesforce VMware چاہتے ہیں یاہو
لڑی Zynga

مسئلہ یہ بیان  

"صف میں زیادہ سے زیادہ دہرانے والے نمبر تلاش کریں" میں ہم نے غیر ترتیب شدہ مسئلہ پیش کیا ہے صف سائز N. دیئے جانے والے صف میں حد {0، k} کی تعداد ہوتی ہے جہاں k <= N. وہ تعداد تلاش کریں جو صف میں زیادہ سے زیادہ تعداد میں آرہی ہو۔

ان پٹ فارمیٹ  

پہلی اور صرف ایک لائن جس میں ایک عددی n ہو۔

دوسری جگہ جس میں ن اسپیس سے الگ الگ عددی شامل ہے جس میں ان پٹ صف کو ظاہر کرنا ہے۔

آؤٹ پٹ کی شکل  

پہلی اور صرف ایک لائن جس میں عددی اعداد پر مشتمل اعداد پر مشتمل ہے جو صف میں زیادہ سے زیادہ بار آرہا ہے۔

رکاوٹوں  

  • 1 <= n <= 10 ^ 6
  • 1 <= a [i] <= n

مثال کے طور پر  

13
2 3 3 4 4 5 5 3 3 6 7 8 3
3

وضاحت: 3 دیئے گئے صف میں کسی بھی تعداد سے 5 گنا زیادہ سے زیادہ آرہی ہے۔

5
2 5 4 3 2
2

وضاحت: 2 دیئے گئے صف میں کسی بھی تعداد سے 2 گنا زیادہ سے زیادہ آرہی ہے۔

الگورتھم  

  •  عنصر کے ذریعہ دیئے گئے سرنی عنصر کے ذریعہ Iterate۔
  • صف میں موجود ہر عنصر کے لئے ہم سرنی کرتے ہیں [سرنی [i]٪ n] = سرنی [سرنی [i]٪ n] + n۔
  • سرنی میں تکرار مکمل کرنے کے بعد ، سرنی میں زیادہ سے زیادہ عنصر کا اشاریہ تلاش کریں۔
  • انڈیکس زیادہ سے زیادہ دہرانے والا عنصر ہے۔
  • اصل سرنی واپس حاصل کرنے کے ل all ، تمام عناصر کے ل for کریں ، سرنی [i] = سرنی [i]٪ k

عمل  

صف میں زیادہ سے زیادہ دہرانے والے نمبر تلاش کرنے کے لئے سی ++ پروگرام

#include <bits/stdc++.h>
using namespace std;

int MaxRepertingElement(int* array, int n)
{
  //modify the array 
  for (int i = 0; i< n; i++)
  {
    array[array[i]%n] += n;
  }
  int max_element = INT_MIN,result = 0;
  for (int i = 0; i < n; i++)
  {
    if (array[i] > max_element)
    {
      max_element = array[i];
      result = i;
    }
  }
  //get the array back to original values
  for (int i = 0; i< n; i++)
  {
    array[i] = array[i]%n; 
  }
  return result;
}

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<MaxRepertingElement(a, n)<<endl;
    return 0;
}

صف میں زیادہ سے زیادہ دہرانے والا نمبر تلاش کرنے کے لئے جاوا پروگرام

import java.util.Scanner;
class sum
{
    //Rearrange function  
    public static int MaxRepertingElement(int array[], int n)
    {
      //modify the array 
      for (int i = 0; i< n; i++)
      {
        array[array[i]%n] += n;
      }
      int max_element = -1,result = 0;
      for (int i = 0; i < n; i++)
      {
        if (array[i] > max_element)
        {
          max_element = array[i];
          result = i;
        }
      }
      //get the array back to original values
      for (int i = 0; i< n; i++)
      {
        array[i] = array[i]%n; 
      }
      return result;
    }
    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 ans = MaxRepertingElement(a, n);
        System.out.println(ans);
    }
}
5
1 1 1 2 3
1

پیچیدگی کا تجزیہ  

وقت کی پیچیدگی

اے (ن) کہاں n دیئے گئے صف کا سائز ہے۔ یہاں ہم صرف پوری صف کو عبور کرتے ہیں اور ہر مقام کے ل constant مستقل وقت میں آپریشن انجام دیتے ہیں۔

یہ بھی دیکھتے ہیں
حتی کہ نمبروں کے ذیلی سیٹ گنتی کریں

خلائی پیچیدگی

O (1) کیونکہ ہم یہاں کوئی معاون جگہ استعمال نہیں کرتے ہیں۔