주어진 시퀀스에 존재하지 않는 증가하는 시퀀스의 k 번째 누락 요소-TutorialCup

Twitter Facebook 링크드 인 버퍼 레딧 텀블러

"주어진 시퀀스에 존재하지 않는 증가하는 시퀀스에서 k 번째 누락 요소"문제는 두 개의 배열이 제공된다는 것을 나타냅니다. 그들 중 하나는 오름차순으로 배열되고 또 다른 일반 정렬되지 않은 배열은 숫자 k입니다. 정상 시퀀스에는 없지만 오름차순 시퀀스 배열에는 존재하는 k 번째 누락 요소를 찾습니다.

차례

예

핀

[0, 2, 4, 6, 8, 10, 12, 14]
[4, 10, 6, 12, 2 ]
k=2

설명

주어진 배열에없는 증가하는 시퀀스의 숫자는 0,8,14입니다.

K 개의^th 누락 된 번호 즉, 2^nd 숫자는 8

주어진 시퀀스에 존재하지 않는 증가하는 시퀀스에서 k 번째 누락 요소를 찾는 알고리즘

선언 해시셋.
두 번째 배열의 모든 요소를 HashSet에 넣습니다.
세트 누락 수 0합니다.
증가하는 순차적 배열을 탐색하는 동안 다음을 확인하십시오.
1. 집합에 순차 배열 요소가 포함되어 있지 않은 경우
  1. missingCount 값을 1 씩 늘립니다.
  2. missingCount 값이 k와 같은지 확인하십시오.
    - 참이면 해당 배열 [i]을 반환합니다.
루프에서 -1을 반환합니다.

설명

두 개의 배열과 숫자 k가 주어집니다. 두 배열 중 하나는 증가하는 시퀀스이고 다른 하나는 정렬되지 않은 정상적인 시퀀스입니다. 문제 설명은 정렬되지 않은 배열에없는 정렬 된 시퀀스 배열에서 k 번째 누락 된 요소를 찾아야한다고 말합니다.

이를 위해 세트를 사용할 것입니다. 두 번째 배열을 탐색 할 것입니다. 비[] 모든 값을 세트에 삽입합니다. 나중에 확인하고 첫 번째 배열과 세트를 비교할 수 있기 때문입니다. ㅏ[]. 배열 a []를 순회하는 동안 집합에 배열 a [i]의 특정 값이 포함되어 있지 않은 경우. 우리는 가치를 증가시킵니다 누락 수 1 씩 동시에 missingCount가 주어진 숫자 k와 같은지 확인합니다. 그렇다면 첫 번째 배열의 해당 요소를 반환 할 수 있습니다.

한 가지 예를 살펴보고 이해해 보겠습니다.

예

배열 a [] = [0, 2, 4, 6, 8, 10, 12, 14]

b [] = [4, 10, 6, 12, 2]

k = 2

알고리즘에 따라 배열 b [] 요소를 집합에 넣어야합니다. 배열 b []를 탐색하여이를 수행합니다.

세트는 {4, 10, 6, 12, 2}가됩니다.

배열 a [] 요소를 순회하고 set에 arr [i] 요소가 포함되어 있지 않은지 확인해야합니다.

i = 0, arr [i] = 0

세트에 포함되지 않으므로 missingCount = missingCount + 1이 증가합니다.

missingCount = 1, missingCount == k, false인지 확인합니다.

i = 1, arr [i] = 2

set에는 해당 값 '2'가 포함되어 있으므로 아무것도하지 않습니다.

i = 2, arr [i] = 4

set에는 해당 값 '4'가 포함되어 있으므로 아무것도하지 않습니다.

i = 3, arr [i] = 6

set에는 해당 값 '6'가 포함되어 있으므로 아무것도하지 않습니다.

i = 4, arr [i] = 8

세트에 8이 포함되어 있지 않으므로 missingCount = missingCount + 1이 증가합니다.

missingCount = 2, missingCount == k인지 확인합니다. true이므로 '8'인 arr [i]를 반환합니다.

출력은 8이됩니다.

암호

주어진 시퀀스에 존재하지 않는 증가하는 시퀀스에서 k 번째 누락 요소를 찾는 C ++ 코드

#include <unordered_set>
#include<iostream>

using namespace std;
int find(int A[], int B[], int k, int l1, int l2)
{
  unordered_set<int> myset;
  for (int i = 0; i < l2; i++)
    myset.insert(B[i]);

  int missingCount = 0;
  for (int i = 0; i < l1; i++) {
    if (myset.find(A[i]) == myset.end())
      missingCount++;
    if (missingCount == k)
      return A[i];
  }

  return -1;
}
int main()
{
    int a[] = { 0, 2, 4, 6, 8, 10, 12, 14};
    int b[] = { 4, 10, 6, 12, 2 };

  int l1 = sizeof(a) / sizeof(a[0]);
  int l2 = sizeof(b) / sizeof(b[0]);

  int k = 2;
  cout << find(a, b, k, l1, l2);
  return 0;
}

주어진 시퀀스에 존재하지 않는 증가하는 시퀀스에서 k 번째 누락 된 요소를 찾는 Java 코드

import java.util.LinkedHashSet;

class kthMissingElement
{
    public static int getMissingElement(int A[], int B[], int k, int l1, int l2)
    {
        LinkedHashSet<Integer> hashset = new LinkedHashSet<>();
        for (int i = 0; i < l2; i++)
            hashset.add(B[i]);

        int missingCount = 0;
        for (int i = 0; i < l1; i++)
        {
            if(!hashset.contains(A[i]) )
                missingCount++;
            if (missingCount == k)
                return A[i];
        }

        return -1;
    }
    public static void main(String[] args)
    {
        int a[] = { 0, 2, 4, 6, 8, 10, 12, 14};
        int b[] = { 4, 10, 6, 12, 2 };
        int l1 = a.length;
        int l2 = b.length;

        int k = 2;
        System.out.println(getMissingElement(a, b, k, l1, l2));
    }
}

복잡성 분석

시간 복잡성

O (n1 + n2) 어디에 "n1" 및 "n2" array1 및 array2의 길이입니다. 두 배열의 모든 요소를 순회했기 때문입니다. 시간 복잡도는 선형입니다.

공간 복잡성

O (n2) 어디에 "n2" array2의 길이입니다. 두 번째 배열의 요소 만 HashSet에 저장했기 때문에 필요한 공간도 선형입니다.

Twitter Facebook 링크드 인 버퍼 레딧 텀블러