배열을 1에서 N까지의 숫자 순열로 변경

이 문제에서 우리는 정렬 n 개의 요소 중 A. 배열의 최소 교체를 사용하여 배열을 1에서 n까지의 숫자 순열로 변경해야합니다.

예

입력:

2 2 3 3

출력:

2 1 3 4

입력 :

3 2 1 7 8 3

출력:

3 2 1 4 5 6

배열을 1에서 N까지의 숫자 순열로 변경하는 주요 아이디어

먼저 누락 된 모든 요소를 ​​세트에 저장합니다. 그 후, 우리는 인쇄했는지 여부를 저장할 해시 테이블을 유지하고 이미 요소를 인쇄하고 배열에 다시 오면이 요소 대신 누락 된 요소를 인쇄해야합니다. 세트에서 요소를 인쇄 한 다음 세트에서 해당 요소를 지 웁니다.

암호알고리즘

1. 1에서 n까지의 모든 숫자 집합을 만드십시오.
2. 배열을 반복하고 집합에서 모든 배열 요소를 제거합니다.
3. 해시 테이블을 선언하고 모든 값을 false로 초기화합니다.
4. 범위 1에서 n-1까지 I에 대한 배열을 반복합니다.
   • arr [i]를 인쇄하지 않은 경우 arr [i]를 인쇄하고 해시 테이블에서 true로 표시합니다.
   • 그렇지 않으면 이미 arr [i]를 인쇄 한 경우 세트에서 첫 번째 요소를 인쇄하고 해당 요소를 세트에서 제거하십시오.
5. 반환.

배열을 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

배열을 1에서 N까지의 숫자 순열로 변경하기위한 복잡성 분석

시간 복잡성

O (NlogN) 누락 된 요소 집합을 준비하기 위해 1에서 n까지 반복하고 각 삽입에 logn 시간이 걸리므로 총 시간 복잡도는 O (N * logN)입니다.

공간 복잡성

의 위에) 여기서 우리는 크기 N의 추가 세트와 해시 테이블을 가져 왔기 때문에 공간 복잡성은 O (N)입니다.

참조