면접 훈련 O (n) 시간의 정렬
사고: 병합, 빠 른 배열, 삽입, 등 정렬 이 가장 빠 른 o (nlgn) 의 시간 복잡 도
o (n) 에 도달 하려 면 시간 복잡 도 는 계수 정렬, 통 정렬, 기수 정렬 법 만 도달 할 수 있 습 니 다.
회사 직원 의 입사 와 이 직 연령 범 위 는 모두 1 - 100 사이 의 수 라 는 점 을 감안 하여 계산 순 서 를 통 해 문 제 를 해결 할 수 있다.
그렇다면 계산 순 서 는 도대체 어떤 생각 일 까? 물론 해시 표 와 유사 한 배열 로 직원 표 에 해당 하 는 연령 대 에 대응 하 는 사람의 수 + 1 을 옮 겨 다 니 면 모든 연령 대 에 대응 하 는 사람 수 를 얻 을 수 있다.
그 다음 에 중첩 을 한다. 예 를 들 어 나이 가 26 세인 직원 은 배열 의 어느 위치 에 배치 해 야 합 니까? 당연히 26 세 이하 와 26 세 이하 의 인원 을 합 친 것 입 니 다. 이 위 치 는 마지막 나이 가 26 인 직원 의 위치 입 니 다. 물론 나중에 직원 들 이 해당 하 는 위치 에 가입 할 수 있 습 니 다. - 1. 26 세 직원 이 처 한 구간 에 속 합 니 다.
마지막 으로 나이 에 따라 필요 한 배열 의 위치 에 관련 요 소 를 넣 으 면 된다.
코드 는 다음 과 같다.
#include "stdio.h"
#define MAX 100
int main()
{
int age[MAX];
int employee[] = {22,37,23,35,19,55,22,33,23,33,37,38};
int i;
int *temp = NULL;
int len = sizeof(employee)/sizeof(int);
temp = calloc(len,sizeof(int));
memset(age,0,sizeof(int)*MAX);
for(i=len-1;i>=0;i--)
{
age[employee[i]] = age[employee[i]]+1;
// printf("i %d emp %d age %d
",i,employee[i],age[employee[i]]);
}
for(i=1;i<MAX;i++)
{
age[i]=age[i]+age[i-1];
}
for(i = len-1;i>=0;i--)
{
temp[age[employee[i]]-1]=employee[i];
age[employee[i]] = age[employee[i]] -1;
}
for(i=0;i<len;i++)
{
printf("%d ",temp[i]);
}
free(temp);
return 0;
}타 오 형의 생각 을 봤 어 요.
그 는 상 반 된 각도 에서 문 제 를 고려 하여, 나이 가 어린 것 에서 나이 가 많은 것 으로 줄 을 섰 다.
모든 연령 대의 인원 을 기록 할 수 있 지만 겹 치지 않 아 도 됩 니 다. 나이 가 어 릴 때 부터 나이 가 많 을 때 까지 같은 연령 대 를 사용 하 는 것 은 누적 일 뿐 입 니 다. 배열 에 반복 해서 추가 하 는 것 이 죠.
코드 는 다음 과 같 습 니 다:
#include "stdio.h"
#define MAX 100
int main()
{
int age[MAX];
int employee[] = {22,37,23,35,19,55,22,33,23,33,37,38};
int i,j;
int index;
int *temp = NULL;
int len = sizeof(employee)/sizeof(int);
temp = calloc(len,sizeof(int));
memset(age,0,sizeof(int)*MAX);
for(i=len-1;i>=0;i--)
{
age[employee[i]] = age[employee[i]]+1;
}
index = 0;
for(i=0;i<MAX;i++) /*O(MAX*n) o(n)*/
{
for(j =0;j<age[i];j++)
{
temp[index]=i;
index++;
}
}
for(i=0;i<index;i++)
{
printf("%d ",temp[i]);
}
free(temp);
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
