실 종 된 정수 배열 찾기 (Find the missing integer)

배열 a 는 N 분 자 를 포함 하고 그 요 소 는 [0, N] 사이 에 속 하 며 반복 되 는 요소 가 존재 하지 않 습 니 다.배열 에 부족 한 요소 ([0, N] 사이 에 N + 1 개의 요소 가 있 기 때문에 배열 은 N 개의 요소 만 저장 할 수 있 습 니 다. 따라서 하나의 요소 가 부족 합 니 다) 를 찾 아 보 세 요.그 중에서 배열 의 조작 은 다음 과 같은 조건 을 만족 시 킵 니 다. 상수 시간 내 에 배열 의 요 소 를 읽 을 수 없 지만 배열 의 요소 의 특정한 bit 값 을 읽 을 수 있 습 니 다.상수 시간 내 에 배열 의 두 원소 의 위 치 를 교환 할 수 있다.선형 시간 내 에 배열 에 부족 한 요 소 를 찾 을 수 있 도록 알고리즘 을 설계 하 십시오.
(N=2^k)
An array a[] contains all of the integers from 0 to N, except 1. However, you cannot access an element with a single operation. Instead, you can call get(i, k) which returns the kth bit of a[i] or you can call swap(i, j) which swaps the ith and jth elements of a[]. Design an O(N) algorithm to find the missing integer. For simplicity, assume N is a power of 2
알고리즘 디자인: 문제 설정 을 통 해 알 수 있 듯 이 [0, N] 사이 의 홀수 와 짝수 의 차 이 는 1 과 같 고 짝수 가 부족 하 다 고 가정 하면 홀수 와 짝수 의 수량 이 같 으 며 반대로 홀수 가 부족 하 다.
어떻게 원소 의 패 리 티 를 추정 합 니까?문제 설정 은 상수 시간 내 에 배열 요소 에 만 접근 할 수 있 는 bit 값 을 보 여 줍 니 다.그래서 원소 의 마지막 bit 가 0 인지 1 인지 만 보면 된다.이렇게 하면 한 번 의 스캐닝 배열 을 통 해 n / 2 개의 요 소 를 제거 할 수 있다.
이 방법 을 이용 하면 우 리 는 부족 한 원 소 를 찾 을 수 있다.상술 한 조작 을 반복 하면 된다.
알고리즘 성능 분석:
첫 번 째 스 캔 원 소 는 패 리 티 를 추정 합 니 다.n 회 순환 해 야 합 니 다.따라서 n / 2 개의 요 소 를 제거 하기 때문에 두 번 째 순환 은 n / 2 회 순환 하고 한 번 유추 해 야 한다.총 순환 횟수 는 T 입 니 다.
T=n+n/2+n/4+n/8+……+1=O(n)。이 를 위해 제목 의 요구 에 도달 했다.
알고리즘 구현:

void swap(int* a, int i, int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}
int get(int* a, int i, int k)
{
	int res = a[i]>>k & 1;
	return res;
}
int Find_the_missing_integer(int* a, int low, int high)
{
	int res = 0;
	int power = 1;
	int count0 = 0;
	int count1 = 0;
	int n = high-low+1;
	int pointer0 = 0;
	int i=0;
	while(n>0)
	{
		for(int j=low; j<=high;j++)
		{
			if(get(a,j,i) == 0)
			{
				count0++;
				swap(a,j,pointer0);
				pointer0++;
			}
			else
			{
				count1++;
			}
		}
		if(count0>count1)
		{
			res = res + power*1;
			low = pointer0;
			n = count1;
		}
		else
		{
			res = res + power*0;
			high = pointer0 - 1;
			pointer0 = low;
			n = count0;
		}
		power = power*2;
		count0 = 0;
		count1 = 0;
		i++;
	}
	return res;
}

알고리즘 해석: findthe_missing_intger, 함수 에서 pointer 를 이용 하여 마지막 요소 의 0 또는 1 의 경계 점 을 기록 합 니 다.그리고 매번 우리 가 요구 하 는 일부 요 소 를 순환 적 으로 스 캔 하여 마침내 요소 의 위치 가 없 을 때 까지 만족 시 킵 니 다.
테스트 코드:

#include <iostream>
using namespace std;
void swap(int* a, int i, int j);
int get(int* a, int i, int k);
int Find_the_missing_integer(int* a, int low, int high);
void main()
{
	int a[]={1,2,3,4,5,6,7,0};
	cout<<Find_the_missing_integer(a,0,7);
}

잘 모 르 시 면 토론 을 환영 합 니 다.
저작권 성명: 본 블 로그 의 오리지널 글, 블 로그, 동의 없 이 전재 할 수 없습니다.