溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了Java基于分治算法實現的線性時間選擇操作。分享給大家供大家參考，具體如下：
線性時間選擇問題：給定線性序集中n個元素和一個整數k，1≤k≤n，要求找出這n個元素中第k小的元素，（這里給定的線性集是無序的）。
隨機劃分線性選擇
線性時間選擇隨機劃分法可以模仿隨機化快速排序算法設計。基本思想是對輸入數組進行遞歸劃分，與快速排序不同的是，它只對劃分出的子數組之一進行遞歸處理。
程序解釋：利用隨機函數產生劃分基準，將數組a[p:r]劃分成兩個子數組a[p:i]和a[i+1:r]，使a[p:i]中的每個元素都不大于a[i+1:r]中的每個元素。接著"j=i-p+1"計算a[p:i]中元素個數j.如果k<=j，則a[p:r]中第k小元素在子數組a[p:i]中，如果k>j，則第k小元素在子數組a[i+1:r]中。注意：由于已知道子數組a[p:i]中的元素均小于要找的第k小元素，因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。
在最壞的情況下，例如：總是找到最小元素時，總是在最大元素處劃分，這是時間復雜度為O(n^2)。但平均時間復雜度與n呈線性關系，為O(n)
package math;
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 = temp;
}
public int Random (int x, int y) {
Random random = new Random();
int num = random.nextInt(y)%(y - x + 1) + x;
return num;
}
public int partition(int[] list, int low, int high) {
int tmp = list[low]; //數組的第一個作為中軸
while (low < high) {
while (low < high && list[high] > tmp) {
high--;
}
list[low] = list[high]; //比中軸小的記錄移到低端
while (low < high && list[low] < tmp) {
low++;
}
list[high] = list[low]; //比中軸大的記錄移到高端
}
list[low] = tmp; //中軸記錄到尾
return low; //返回中軸的位置
}
public int RandomizedPartition (int[] arrays, int left, int right) {
int i = Random(left, right);
swap(arrays[i], arrays[left]);
return partition(arrays, left, right);
}
public int RandomizedSelect(int[] arrays, int left, int right, int k) {
if(left == right ) {
return arrays[left];
}
int i = RandomizedPartition(arrays, left, right);
int j = i - left + 1;
if(k <= j) {
return RandomizedSelect(arrays,left, i,k) ;
}
else {
return RandomizedSelect(arrays,i+1,right,k-j);
}
}
public static void main(String args[]) {
System.out.println("億速云測試結果：");
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")
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = r.RandomizedSelect(a,0,8,m);
System.out.println("這個數組中第" + m + "小的元素是："+ n);
}
}
運行結果：
更多關于java算法相關內容感興趣的讀者可查看本站專題：《Java數據結構與算法教程》、《Java操作DOM節點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
