程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C說話輸入扭轉後數組中的最小數元素的算法道理與實例

C說話輸入扭轉後數組中的最小數元素的算法道理與實例

編輯:關於C++

C說話輸入扭轉後數組中的最小數元素的算法道理與實例。本站提示廣大學習愛好者:(C說話輸入扭轉後數組中的最小數元素的算法道理與實例)文章只能為提供參考,不一定能成為您想要的結果。以下是C說話輸入扭轉後數組中的最小數元素的算法道理與實例正文


  成績描寫:把一個數組最開端的若干個元素搬到數組的末尾,我們稱之為數組的扭轉。輸出一個排好序的數組的一個扭轉,輸入扭轉數組的最小元素。例如數組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個扭轉,該數組的最小值為1。
     思緒:這道題最直不雅的解法其實不難。從頭至尾遍歷數組一次,就可以找出最小的元素,時光龐雜度明顯是O(n)。但這個思緒沒有益用輸出數組的特征。既然有時光龐雜度更小的算法,我們輕易想到二分查找,由於它的時光龐雜度為O(logn)。這個成績能否可以應用二分查找呢?謎底是確定的。不雅察一下數組的特征,起首遞增(稱為遞增a),然後忽然降低到最小值,然後再遞增(稱為遞增b)。固然還有一種特別情形,就是數組遞增,中央沒有降低,即扭轉元素個數為0。
      關於普通的情形,假定A為輸出數組,left 和 right 為數組閣下界限的坐標,考核中央地位的值A[mid] ,假如A[mid] <= A[right],注解處於遞增b,調劑左邊界 right = mid;假如A[mid] >= A[left],注解處於遞增a,是以調劑右邊界left = mid。當閣下界限相鄰時,較小的一個就是數組的最小值。其實,關於普通情形,左邊界所指的元素為最小值。
     關於特別情形,即扭轉個數為0。依照上述算法,左邊界會赓續削減,直到與右邊界相鄰。這時候右邊界所指的元素為最小值。上面給出幾組測試案例:

//{1,2,3,4,5,6,7,8,9,10}  1 
//{4,5,6,7,8,9,10,1,2,3}  1 
//{1,1,1,1,1,1,1,1,1,1}  1 
//{1,9,10,1,1,1,1,1,1,1}  1 
//{9,9,9,9,9,9,9,10,1,9}  9 毛病 

 
     第五組的成果是毛病的。其實,上述算法實用於嚴厲遞增的數組,關於非嚴厲遞增,用二分法沒法包管准確解。有興致的讀者,可以嘗嘗,關於非嚴厲遞增的序列,能否可以用二分法獲得准確解。
     參考代碼:

//函數功效 : 扭轉數組的最小元素  
//函數參數 : pArray指向數組,len為數組長度 
//前往值 :  最小元素 
int FindMin(int *pArray, int len) 
{ 
  if(pArray == NULL || len <= 0) 
    return 0; 
  int left = 0, right = len - 1, mid; 
  while(right - left != 1) 
  { 
     mid = left + ((right - left)>>1); 
     if(pArray[right] >= pArray[mid])  
       right = mid; 
     else if(pArray[left] <= pArray[mid])     
       left = mid; 
  } 
  return pArray[right] > pArray[left] ? pArray[left]: pArray[right]; 
} 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved