您好,登錄后才能下訂單哦!
本文實(shí)例講述了Java基于分治算法實(shí)現(xiàn)的線性時(shí)間選擇操作。分享給大家供大家參考,具體如下:
線性時(shí)間選擇問題:給定線性序集中n個(gè)元素和一個(gè)整數(shù)k,1≤k≤n,要求找出這n個(gè)元素中第k小的元素,(這里給定的線性集是無序的)。
隨機(jī)劃分線性選擇
線性時(shí)間選擇隨機(jī)劃分法可以模仿隨機(jī)化快速排序算法設(shè)計(jì)?;舅枷胧?span >對輸入數(shù)組進(jìn)行遞歸劃分,與快速排序不同的是,它只對劃分出的子數(shù)組之一進(jìn)行遞歸處理。
程序解釋:利用隨機(jī)函數(shù)產(chǎn)生劃分基準(zhǔn),將數(shù)組a[p:r]劃分成兩個(gè)子數(shù)組a[p:i]和a[i+1:r],使a[p:i]中的每個(gè)元素都不大于a[i+1:r]中的每個(gè)元素。接著"j=i-p+1"計(jì)算a[p:i]中元素個(gè)數(shù)j.如果k<=j,則a[p:r]中第k小元素在子數(shù)組a[p:i]中,如果k>j,則第k小元素在子數(shù)組a[i+1:r]中。注意:由于已知道子數(shù)組a[p:i]中的元素均小于要找的第k小元素,因此,要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。
在最壞的情況下,例如:總是找到最小元素時(shí),總是在最大元素處劃分,這是時(shí)間復(fù)雜度為O(n^2)。但平均時(shí)間復(fù)雜度與n呈線性關(guā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]; //數(shù)組的第一個(gè)作為中軸 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("億速云測試結(jié)果:"); 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("你要查詢的元素是數(shù)組中第幾小的?"); @SuppressWarnings("resource") Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = r.RandomizedSelect(a,0,8,m); System.out.println("這個(gè)數(shù)組中第" + m + "小的元素是:"+ n); } }
運(yùn)行結(jié)果:
更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設(shè)計(jì)有所幫助。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。