ផ្លាស់ប្តូរអារេទៅជាការអនុញ្ញាតិលេខពីលេខ ១ ដល់អិន


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ Capgemini ដេលីវ៉ាយ Fourkites MAQ o9 ដំណោះស្រាយ ការផ្សព្វផ្សាយជាសាធារណៈ
អារេ ហាស់ គណិតវិទ្យា ការស្វែងរក

នៅក្នុងបញ្ហានេះយើងបានផ្តល់ឱ្យ អារេ ធាតុមួយនៃ n ។ យើងត្រូវផ្លាស់ប្តូរអារេទៅជាការអនុញ្ញាតិលេខពីលេខ ១ ដល់លេខ n ដោយប្រើការជំនួសអប្បបរមានៅក្នុងអារេ។

ឧទាហរណ៍

បញ្ចូល:

2 2 3 3

លទ្ធផល:

2 1 3 4

ការបញ្ចូល៖

3 2 1 7 8 3

លទ្ធផល:

3 2 1 4 5 6

គំនិតចម្បងសម្រាប់ផ្លាស់ប្តូរអារេទៅជាការអនុញ្ញាតិលេខពីលេខ ១ ដល់អិន

ដំបូងយើងនឹងរក្សាទុកធាតុដែលបាត់ទាំងអស់ក្នុងសំណុំមួយ។ បន្ទាប់ពីនោះយើងនឹងរក្សាតារាងហាសដែលនឹងរក្សាទុកថាតើយើងបានបោះពុម្ពរឺអត់ហើយប្រសិនបើយើងបានបោះពុម្ពធាតុរួចហើយហើយវាកើតឡើងជាថ្មីម្តងទៀតនោះមានន័យថាយើងត្រូវបោះពុម្ពធាតុដែលបាត់ជំនួសធាតុនេះដូច្នេះយើងនឹង បោះពុម្ពធាតុមួយចេញពីសំណុំរបស់យើងហើយបន្ទាប់មកលុបធាតុនោះចេញពីសំណុំរបស់យើង។

ក្បួនដោះស្រាយ

  1. ធ្វើសំណុំនៃលេខទាំងអស់ពីលេខ 1 ដល់លេខ n;
  2. ច្របាច់អារេហើយយកធាតុអារេទាំងអស់ចេញពីសំណុំ។
  3. ប្រកាសតារាងហាសហើយចាប់ផ្តើមតម្លៃរបស់វាទាំងអស់ដោយមិនពិត។
  4. បែងចែកអារេសម្រាប់ខ្ញុំនៅក្នុងជួរទី 1 ដល់ n-1
    • ប្រសិនបើយើងមិនបានបោះពុម្ពព្រីន [i] ទេនោះព្រីនព្រីន [i] ហើយសម្គាល់វាថាពិតនៅក្នុងតារាងហាស។
    • ប្រសិនបើយើងបានបោះពុម្ពរួចហើយ [i] បន្ទាប់មកបោះពុម្ពធាតុទីមួយចេញពីសំណុំហើយយកធាតុនោះចេញពីសំណុំ។
  5. ត្រឡប់។

ការអនុវត្តសម្រាប់ការផ្លាស់ប្តូរអារេទៅជាការអនុញ្ញាតិលេខពីលេខ ១ ដល់អិន

កម្មវិធី C ++

#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

ការវិភាគស្មុគស្មាញសម្រាប់ការផ្លាស់ប្តូរអារេទៅជាការអនុញ្ញាតិលេខពីលេខ ១ ដល់អិន

ភាពស្មុគស្មាញពេលវេលា

O (NlogN) ពីព្រោះដើម្បីរៀបចំសំណុំធាតុដែលបាត់យើងធ្វើចាប់ពី ១ ដល់ n ហើយការបញ្ចូលនីមួយៗត្រូវការពេលវេលាដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាសរុបគឺ O (N * logN) ។

ភាពស្មុគស្មាញនៃលំហ

O (N) ពីព្រោះនៅទីនេះយើងបានយកសំណុំបន្ថែមនិងតុមួយដែលមានទាំងទំហំ N ដូច្នេះភាពស្មុគស្មាញរបស់យើងគឺ O (N)

ឯកសារយោង