ປ່ຽນ Array ເປັນການອະນຸຍາດຕົວເລກນັບຕັ້ງແຕ່ 1 ເຖິງ N


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Capgemini ເດລີ ສີ່ພັນ MAQ o9 ວິທີແກ້ໄຂ ການໂຄສະນາເຜີຍແຜ່
Array Hash ຄະນິດສາດ ຊອກຫາ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ໃຫ້ array A ຂອງອົງປະກອບ n. ພວກເຮົາ ຈຳ ເປັນຕ້ອງປ່ຽນແປງອາເລນເປັນຕົວເລືອກຂອງຕົວເລກຈາກ 1 ເຖິງ n ໂດຍໃຊ້ການທົດແທນຂັ້ນຕ່ ຳ ໃນແຖວ.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ:

2 2 3 3

ຜົນໄດ້ຮັບ:

2 1 3 4

Input:

3 2 1 7 8 3

ຜົນໄດ້ຮັບ:

3 2 1 4 5 6

ແນວຄວາມຄິດຫຼັກ ສຳ ລັບການປ່ຽນ Array ເຂົ້າໃນການອະນຸຍາດຕົວເລກຈາກ 1 ເຖິງ N

ຫນ້າທໍາອິດ, ພວກເຮົາຈະເກັບຮັກສາອົງປະກອບທີ່ຂາດຫາຍໄປທັງຫມົດໃນຊຸດ. ຫລັງຈາກນັ້ນ, ພວກເຮົາຈະຮັກສາຕາຕະລາງ hash ເຊິ່ງຈະເກັບຮັກສາໄວ້ບໍ່ວ່າພວກເຮົາໄດ້ພິມຫລືບໍ່ແລະຖ້າພວກເຮົາໄດ້ພິມອົງປະກອບໃດ ໜຶ່ງ ແລ້ວແລະມັນຈະມາອີກໃນແຖວນັ້ນມັນ ໝາຍ ຄວາມວ່າພວກເຮົາຕ້ອງໄດ້ພິມອົງປະກອບທີ່ຫາຍໄປແທນທີ່ຈະເປັນອົງປະກອບນີ້ດັ່ງນັ້ນພວກເຮົາຈະ ພິມອົງປະກອບຈາກຊຸດຂອງພວກເຮົາແລະຫຼັງຈາກນັ້ນລົບລ້າງອົງປະກອບນັ້ນອອກຈາກຊຸດຂອງພວກເຮົາ.

ລະບົບວິເຄາະ

  1. ສ້າງຊຸດຂອງຕົວເລກທັງ ໝົດ ຕັ້ງແຕ່ 1 ເຖິງ n;
  2. Iterate array ແລະເອົາທັງຫມົດຂອງ array array ອອກຈາກຊຸດ.
  3. ປະກາດຕາຕະລາງ hash ແລະເລີ່ມຕົ້ນຄ່າທັງ ໝົດ ຂອງມັນດ້ວຍ ຄຳ ປອມ.
  4. ປະສົມອາຫານຂອງ I ໃນຂອບເຂດ 1 ເຖິງ n-1
    • ຖ້າພວກເຮົາບໍ່ໄດ້ພິມ ໜັງ ສື arr [i] ແລ້ວພິມ [[]] ແລະ ໝາຍ ວ່າມັນເປັນຄວາມຈິງຢູ່ໃນຕາຕະລາງ hash.
    • ອື່ນຖ້າພວກເຮົາໄດ້ພິມແລ້ວ [i], ແລ້ວພິມອົງປະກອບ ທຳ ອິດຈາກຊຸດແລະເອົາອົງປະກອບນັ້ນອອກຈາກຊຸດ.
  5. ກັບຄືນ.

ການຈັດຕັ້ງປະຕິບັດເພື່ອປ່ຽນ Array ເຂົ້າໃນການອະນຸຍາດຕົວເລກນັບແຕ່ວັນທີ 1 ເຖິງ N

ໂປຣແກຣມ 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

ໂຄງການ JAVA

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການປ່ຽນ Array ເຂົ້າໃນການອະນຸຍາດຕົວເລກນັບແຕ່ວັນທີ 1 ເຖິງ N

ຄວາມສັບສົນເວລາ

O (NlogN) ເນື່ອງຈາກວ່າການກະກຽມຊຸດຂອງອົງປະກອບທີ່ຂາດຫາຍໄປ, ພວກເຮົາໄດ້ປັບປ່ຽນຈາກ 1 ເຖິງ n, ແລະການແຊກແຕ່ລະຄັ້ງຕ້ອງໃຊ້ເວລາເຂົ້າສູ່ລະບົບ, ສະນັ້ນ, ຄວາມສັບສົນເວລາທັງ ໝົດ ແມ່ນ O (N * logN).

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N) ເນື່ອງຈາກວ່າຢູ່ທີ່ນີ້ພວກເຮົາໄດ້ເອົາແລະພິເສດທີ່ ກຳ ນົດໄວ້ແລະຕາຕະລາງທີ່ມີທັງຂະ ໜາດ N, ສະນັ້ນຄວາມສັບສົນໃນອະວະກາດຂອງພວກເຮົາແມ່ນ O (N)

ເອກະສານ