알고리즘 학습 - K 번 째 큰 숫자 찾기
4441 단어 알고리즘
일반적으로 우 리 는 가장 큰 숫자 와 가장 작은 숫자 를 찾 지만 시간 은 모두 O (N) 급 이다.
여기 서 K 번 째 로 큰 숫자 를 찾 는 방법 은 간단 하 다. 바로 매번 배열 을 두 부분 으로 나 눈 다음 에 K 번 째 로 큰 숫자 가 어느 그룹 에 속 하 는 지 보고 이 그룹 을 찾 아 다른 그룹 을 던 지 는 것 이다.
이 방법 은 빠 른 정렬 과 같 습 니 다. 빠 른 정렬 의 시간 복잡 도 는 O (NLogN) 이기 때 문 입 니 다. 이 방법 은 버 린 절반 을 조작 할 필요 가 없 기 때문에 이 방법 은 NLogN 의 방법 보다 빠 르 고 평균 복잡 도 는 O (n) 에 가 깝 습 니 다.
코드 는 다음 과 같 습 니 다:
//
// main.cpp
// Find_K_Max_Number
//
// Created by Alps on 15/10/23.
// Copyright (c) 2015 chen. All rights reserved.
//
#include <iostream>
#include <vector>
#include <time.h>
using namespace std;
int RandNum(int start, int end);
void SwapArr(int &a, int &b){
a = a+b;
b = a-b;
a = a-b;
}
int FindNum(int start, int end, int * arr, int k){
if (end <= start) {
return arr[end];
}
int cur = RandNum(start, end);
SwapArr(arr[cur], arr[end]);
int i = start, j = start;
for (i = start; i < end; ++i) {
if (arr[i] < arr[end]) {
SwapArr(arr[i], arr[j]);
j++;
}
}
SwapArr(arr[j], arr[end]);
if (j == k-1) {
return arr[j];
}else if (j > k-1) {
return FindNum(start, j-1, arr, k);
}else {
return FindNum(j+1, end, arr, k);
}
}
int RandNum(int start, int end){
if ((end-start) == 0 || end < start) {
return 0;
}
srand((unsigned)time(NULL));
int TEMP_RAND_NUM = rand()%(end-start) + start;
return TEMP_RAND_NUM;
}
int FindKMax(int * arr, int length, int k){
return FindNum(0, length-1, arr, k);
return 0;
}
int main(int argc, const char * argv[]) {
int a[5] = {4,2,1,3,5};
printf("%d
",FindKMax(a, 5, 3));
return 0;
}
이상 코드 는 제 가 테스트 해 봤 습 니 다.당분간 문 제 는 발견 되 지 않 았 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
