면접 문제: 사라진 숫자

4872 단어
제목은: 수조nums는 0에서 n까지의 모든 정수를 포함하지만, 그 중 하나가 부족합니다.코드를 작성해서 그 부족한 정수를 찾아내세요.요구 시간의 복잡도는 O(n)이다.이 문제에서 내가 먼저 생각한 것은 이 수조를 작은 그룹에서 큰 그룹으로 정렬(시간 복잡도 O(n)하는 정렬 알고리즘)한 다음에 0으로 초기화된 변수 j를 수조의 아래에 따라 표시하는 것이다. 변수의 값이 수조에 대응하는 하위 위치의 값과 같지 않을 때 변수 j의 값은 바로'사라진 숫자'이다.뒤에 또 하나의'통'방법이 떠올랐다. 이런 방법은 추가 메모리를 소모해야 하기 때문에 이 방법은 더 이상 말하지 않겠다. 코드는 다음과 같다.
int missingNumber(int *nums,int numsSize){
    int num;
	int *arr=(int *)malloc(sizeof(int)*(numsSize+1));//      
	for(int i=0;i<=numsSize;i++)
	{
		arr[i]=0;// 0-numsSizes      
	}
	for(int i=0;i<numsSize;i++)
	{
		num=nums[i];//           num
		arr[num]=1;// num            1
	}
	for(int i=0;i<=numsSize;i++)
	{
		if(arr[i]==0)//      0,        "     "
		{
			return i;//    
			break;
		}
	}
	free(arr);//       
    return 0;
}
[DFS/BFS] 재귀함수 :: 꼭 필요한 자료구조 기초
C# 인터페이스의 역할 인스턴스 해결

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage