이 기사는 파티셔닝 및 정복 알고리즘을 기반으로 Java가 구현 한 선형 시간 선택 작업에 대해 설명합니다. 다음과 같이 참조에 대해 공유하십시오.
선형 시간 선택 문제 : N 요소와 정수 k, 1≤k≤n이 주어지면, 이들 n 요소의 가장 작은 요소를 찾아야한다 (여기에 주어진 선형 세트는 무질서하다).
무작위로 분할 된 선형 선택
선형 시간 선택 랜덤 디비전 방법은 무작위 빠른 정렬 알고리즘의 설계를 모방 할 수 있습니다. 기본 아이디어는 입력 배열을 되풀이하는 것입니다. 빠른 정렬과 달리 분할 된 서브 어레이 중 하나만 재귀 적으로 처리합니다.
프로그램 설명 : 임의의 함수를 사용하여 디비전 벤치 마크를 생성하고 배열 a [p : r]을 두 개의 서브 배달 a [p : i]와 [i+1 : r]으로 나누어 [p : i]의 각 요소가 [i+1 : r]의 각 요소보다 크지 않도록하십시오. 그런 다음 "j = i-p+1"은 [p : i]에서 요소 j의 수를 계산합니다. k <= j 인 경우, [p : r]에서 가장 작은 요소는 서브 어레이 A [p : i]에 있고, k> j 인 경우, 가장 작은 요소는 하위 배열 a [i+1 : r]에 있습니다. 참고 : 서브 어레이 A [P : I]의 요소가 모두 발견 될 K-th 작은 요소보다 작다는 것이 알려져 있기 때문에, [P : R]의 K-th 작은 요소는 [i+1 : r]의 k-th 작은 요소입니다.
예를 들어 최악의 경우 : 가장 작은 요소가 항상 발견되면 항상 가장 큰 요소로 나뉘어지며, 이는 O (n^2) 의 시간 복잡성입니다. 그러나 평균 시간 복잡성은 n과 선형으로 관련되어 있으며, 이는 O (n) 입니다.
패키지 수학; import java.util.scanner; import java.util.random; public class randomselect {public static void swap (int x, int y) {int temp = x; x = y; y = 온도; } public int random (int x, int y) {random random = new random (); int num = random.nextint (y)%(y -x + 1) + x; Num 리턴; } public int partition (int [] list, int low, int high) {int tmp = list [low]; // 첫 번째 배열은 중심 축입니다. } list [low] = list [High]; // 중심 축보다 작은 레코드는 낮은 엔드로 이동하는 동안 (낮음 <high && list [low] <tmp) {low ++; } list [High] = list [low]; // 중심 축보다 큰 레코드가 하이 엔드로 이동} 목록 [LOW] = TMP; // 중심 축보다 큰 레코드는 낮게 반환됩니다. // 중심 축의 위치로 돌아갑니다} public int randomized -partition (int [] 배열, int 왼쪽, int 오른쪽) {int i = random (왼쪽, 오른쪽); 스왑 (배열 [i], 배열 [왼쪽]); 반환 파티션 (배열, 왼쪽, 오른쪽); } public int randomizedSelect (int [] 배열, int 왼쪽, int right, int k) {if (왼쪽 == 오른쪽) {return array [left]; } int i = 무작위 배열 (배열, 왼쪽, 오른쪽); int j = i- 왼쪽 + 1; if (k <= j) {return randomizedSelect (배열, 왼쪽, i, k); } else {return randomizedSelect (배열, i+1, 오른쪽, KJ); }} public static void main (String args []) {System.out.println ( "wulin.com test result :"); int [] a = {7,5,3,4,8,6,9,1,2}; for (int i = 0; i <9; i ++) {system.out.print (a [i]+""); } system.out.println (); randomselect r = new randomselect (); System.out.println ( "배열에서 쿼리를 원하십니까?"); @SuppressWarnings ( "Resource") 스캐너 sc = 새 스캐너 (System.In); int m = sc.nextint (); int n = R.RandomizedSelect (a, 0,8, m); System.out.println (이 배열의 "TH" " + M +"가장 작은 요소는 : " + N); }}실행 결과 :
Java 알고리즘에 대한 자세한 내용은이 사이트에 관심이있는 독자들이 주제를 볼 수 있습니다. "Java 데이터 구조 및 알고리즘 자습서", "Java Operation Dom Node Tips 요약", "Java 파일 및 디렉토리 작동 팁 요약"및 "Java Cache Operation Tips의 요약"을 볼 수 있습니다.
이 기사가 모든 사람의 Java 프로그래밍에 도움이되기를 바랍니다.