在一位陣列中挑選適應元素
基于java的分治法，
- 問題：一排一維陣列要要求出其中最接近指定數r的相鄰元素和，怎么求？如{1，4，6，3，-2，7}最接近15的元素是{1，4，6，3}最接近5的的元素是{-2，7}
- 先留時間思考一下，如果是你你會怎么做？
先說一種只要上過高中就寫的出的最直觀的方法，我稱之為排列組合法`
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < args.length; j++) {
簡單來說就是把陣列arr[]中相鄰元素的排列組合
取完，然后一一對比取出最接近要求值r的數字
}
}
方法是很直觀，但是時間卻需要花費n^2的個數積，我不同意！
于是我們就可以往分治的方向想：打個比方，小學的時候老師要求選出全班10個男生力氣最大的他絕對不會用排列組合的方法確保每個人都比過一次，而是會讓同學兩兩相比，最后選出優勝者再兩兩相比
那么我們是不是可以這樣想：假設arr有10個元素那么和要求值r最接近的要不在整段的arr【0—9】的中間部分要不就在左邊arr【0-4】要不就在右邊arr【5-9】而左邊陣列arr【0-4】的最佳值也如此要不是本段中間部分要不在左邊arr【0-2】…
直到分為最小的子元素這個時候你講順序倒過來看那么就變成了
那么話不多說最后上代碼
public static int compete(int a,int b,int c,int p){
//a,b,c是需要與p進行比較的三個數
int result=Math.abs(a-p);
int r=a;
if(result>Math.abs(b-p))
{result=Math.abs(b-p);r=b;}
if(result>Math.abs(c-p))
{result=Math.abs(c-p);r=c;}
return r;
}`
public static int divide(int[] arr,int l,int u,int r){
//arr是問題陣列，L是陣列底部，u是陣列頂部，r是被要求比較的數數
if(l>u)
return -10000;
if(l==u)
{
return arr[l];}
int m=(l+u)/2;int t1=0;int t2=1;int suit=-10000;int sum=0;
//m是中值，t1，t2是指標，suit是最適合的數，sum是當前位置求和結果
while((m-t1)==l&&(m+t2)==u){
if((m-t1)==l){
sum+=arr[m+t2];
if(Math.abs(suit-r)>Math.abs(sum-r))
suit=sum;
t2++;
}
else if ((m+t2)==u) {
sum+=arr[m+t1];
if(Math.abs(suit-r)>Math.abs(sum-r))
suit=sum;
t1++;
}
else if(Math.abs(sum+arr[m-t1]-r)>Math.abs(sum+arr[m+t2]-r)){
sum+=arr[m+t2];
if(Math.abs(suit-r)>Math.abs(sum-r))
suit=sum;
t2++;
}
else if(Math.abs(sum+arr[m-t1]-r)>Math.abs(sum+arr[m+t2]-r)){
sum+=arr[m+t1];
if(Math.abs(suit-r)>Math.abs(sum-r))
suit=sum;
t1++;
}
}
return compete(suit, divide(arr, l, m,r), divide(arr, m+1, u,r),r);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int arr[]={4,6,0,46,4,-3,7,-10,-39,-4,-3,12,4,-9,-22,13};
int r=scan.nextInt();
System.out.println(divide(arr, 0, arr.length-1,r));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/232549.html
標籤：java