1 മുതൽ N വരെ അക്കങ്ങളുടെ ക്രമമാറ്റത്തിലേക്ക് അറേ മാറ്റുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു കാപ്ജെമിനിയും ദില്ലി ഫോർകൈറ്റുകൾ MAQ o9 പരിഹാരങ്ങൾ പബ്ലിസിസ് സാപിയന്റ്
അറേ ഹാഷ് മഠം തിരയുന്നു

ഈ പ്രശ്‌നത്തിൽ‌, ഞങ്ങൾ‌ ഒരു നൽകി ശ്രേണി N ഘടകങ്ങളുടെ A. അറേയിലെ മിനിമം മാറ്റിസ്ഥാപനങ്ങൾ ഉപയോഗിച്ച് 1 മുതൽ n വരെയുള്ള സംഖ്യകളുടെ ക്രമമാറ്റത്തിലേക്ക് ഞങ്ങൾ അറേ മാറ്റേണ്ടതുണ്ട്.

ഉദാഹരണം

ഇൻപുട്ട്:

2 2 3 3

ഔട്ട്പുട്ട്:

2 1 3 4

ഇൻപുട്ട്:

3 2 1 XIX XIX 7

ഔട്ട്പുട്ട്:

3 2 1 XIX XIX 4

1 മുതൽ N വരെ നമ്പറുകളുടെ ക്രമമാറ്റത്തിലേക്ക് അറേ മാറ്റുന്നതിനുള്ള പ്രധാന ആശയം

ആദ്യം, നഷ്‌ടമായ എല്ലാ ഘടകങ്ങളും ഒരു സെറ്റിൽ ഞങ്ങൾ സംഭരിക്കും. അതിനുശേഷം, ഞങ്ങൾ ഒരു ഹാഷ് പട്ടിക പരിപാലിക്കും, അത് ഞങ്ങൾ അച്ചടിച്ചിട്ടുണ്ടോ ഇല്ലയോ എന്ന് സംഭരിക്കും, ഞങ്ങൾ ഇതിനകം ഒരു ഘടകം അച്ചടിച്ചിട്ടുണ്ടെങ്കിൽ അത് വീണ്ടും അറേയിൽ വരുന്നുവെങ്കിൽ അതിനർത്ഥം ഈ ഘടകത്തിന് പകരം നഷ്‌ടമായ ഒരു ഘടകം പ്രിന്റുചെയ്യേണ്ടതുണ്ട്, അതിനാൽ ഞങ്ങൾ ചെയ്യും ഞങ്ങളുടെ സെറ്റിൽ നിന്ന് ഒരു ഘടകം പ്രിന്റുചെയ്യുക, തുടർന്ന് ഞങ്ങളുടെ സെറ്റിൽ നിന്ന് ആ ഘടകം മായ്‌ക്കുക.

അൽഗോരിതം

  1. 1 മുതൽ n വരെയുള്ള എല്ലാ അക്കങ്ങളുടെയും ഒരു കൂട്ടം ഉണ്ടാക്കുക;
  2. അറേ ആവർത്തിച്ച് സെറ്റിൽ നിന്ന് എല്ലാ അറേ ഘടകങ്ങളും നീക്കംചെയ്യുക.
  3. ഒരു ഹാഷ് പട്ടിക പ്രഖ്യാപിച്ച് അതിന്റെ എല്ലാ മൂല്യങ്ങളും തെറ്റായി സമാരംഭിക്കുക.
  4. 1 മുതൽ n-1 വരെയുള്ള ശ്രേണിയിലെ എനിക്കായുള്ള അറേ ആവർത്തിക്കുക
    • ഞങ്ങൾ‌ arr [i] അച്ചടിച്ചിട്ടില്ലെങ്കിൽ‌, arr [i] പ്രിന്റുചെയ്‌ത് ഹാഷ് പട്ടികയിൽ‌ അത് ശരിയാണെന്ന് അടയാളപ്പെടുത്തുക.
    • അല്ലെങ്കിൽ ഞങ്ങൾ ഇതിനകം arr [i] പ്രിന്റുചെയ്‌തിട്ടുണ്ടെങ്കിൽ, സെറ്റിൽ നിന്ന് ആദ്യ ഘടകം പ്രിന്റുചെയ്‌ത് സെറ്റിൽ നിന്ന് ആ ഘടകം നീക്കംചെയ്യുക.
  5. മടങ്ങുക.

1 മുതൽ N വരെ അക്കങ്ങളുടെ ക്രമമാറ്റത്തിലേക്ക് അറേ മാറ്റുന്നതിനുള്ള നടപ്പാക്കൽ

സി ++ പ്രോഗ്രാം

#include <bits/stdc++.h>
using namespace std;
void makePermutation(vector<int> a, int n)
{
    set<int> s;
    for (int i = 1; i <= n; i++)
    {
        s.insert(i);
    }
    for (int i = 0; i < n; i++)
    {
        if (s.count(a[i]))
        {
            s.erase(a[i]);
        }
    }
    vector<bool> m(n + 1, false);
    for (int i = 0; i < n; i++)
    {
        if ((a[i] <= n) and (a[i] > 0) and (m[a[i]] == 0))
        {
            m[a[i]] = true;
            cout << a[i] << " ";
        }
        else
        {
            int missing_number = *s.begin();
            m[missing_number] = true;
            s.erase(s.begin());
            cout << missing_number << " ";
        }
    }
    return;
}
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    makePermutation(a, n);
    return 0;
}
2 2 3 3
2 1 3 4

ജാവ പ്രോഗ്രാം

import java.util.*;
public class Main
{
    public static void makePermutation(int[] a, int n)
    {
        Set<Integer> s = new HashSet<Integer>(); 
        for (int i = 1; i <= n; i++)
        {
            s.add(i);
        }
        for (int i = 0; i < n; i++)
        {
            if (s.contains(a[i]))
            {
                s.remove(a[i]);
            }
        }
        boolean[] m = new boolean[n+1];
        for (int i = 0; i < n; i++)
        {
            if ((a[i] <= n) && (a[i] > 0) && (m[a[i]] == false))
            {
                m[a[i]] = true;
                System.out.print(a[i]+" ");
            }
            else
            {
                int missing_number = (s.iterator()).next();
                m[missing_number] = true;
                s.remove(missing_number);
                System.out.print(missing_number+" ");
            }
        }
        return;
    }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] a = new int[n];
      for(int i=0;i<n;i++){
          a[i] = sc.nextInt();
      }
      makePermutation(a, n);
  }
}

5
1 5 3 7 6
1 5 3 2 4

1 മുതൽ N വരെ അക്കങ്ങളുടെ ക്രമമാറ്റത്തിലേക്ക് അറേ മാറ്റുന്നതിനുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (NlogN) കാരണം നഷ്‌ടമായ ഘടകങ്ങളുടെ ഗണം തയ്യാറാക്കാൻ, ഞങ്ങൾ 1 മുതൽ n വരെ ആവർത്തിക്കുന്നു, ഒപ്പം ഓരോ ഉൾപ്പെടുത്തലിനും ലോഗ് സമയം എടുക്കും, അതിനാൽ മൊത്തം സമയ സങ്കീർണ്ണത O (N * logN) ആണ്.

സ്ഥല സങ്കീർണ്ണത

O (N) കാരണം ഇവിടെ ഞങ്ങൾ എടുത്തതും അധിക സെറ്റും N വലുപ്പമുള്ള ഹാഷ് ടേബിളും ഉള്ളതിനാൽ ഞങ്ങളുടെ സ്ഥല സങ്കീർണ്ണത O (N) ആണ്

അവലംബം