今天小編給大家分享一下怎么使用C++在無序數組中實現選擇第k小個數的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

成都創新互聯公司堅持“要么做到，要么別承諾”的工作理念，服務領域包括：成都網站設計、成都網站建設、外貿網站建設、企業官網、英文網站、手機端網站、網站推廣等服務，滿足客戶于互聯網時代的淅川網站設計、移動媒體設計的需求，幫助企業找到有效的互聯網解決方案。努力成為您成熟可靠的網絡建設合作伙伴！

從一個無序的整型數組中選出第k小的數，如k=1為最小數，k=n為較大數。這里數組可以是有重復的值！

下面是自己寫的一個函數，記在此處來記憶我留下的痕跡！

//選擇無序數組中第k小的數
#include <iostream>
using namespace std ;
bool failed = false ;
//這里只考慮數組是int型的
int findnumber(int *array,int start , int end, int k)
{
  if(array == NULL || start > end || k < start || k > end+1 || k <= 0 )
  {
    failed = true ;
    return 0;
  }
  if(start == end)
  {
    return array[start] ;
  }
  int len = end - start + 1 ;
  int tmp = 0 ;
  int ps = rand()%len +start ;
  int tk = k ;
  while(true)
  {
   //分割兩數組
   int f = start ;
   int t = array[ps] ;
   int equalnum = 0 ;
   for(int i = start ; i <= end ; i ++ )
   {
        if(array[i]< t )
        {
          tmp = array[f];
          array[f] = array[i];
          array[i] = tmp ;
          f ++ ;
        }else if(array[i] == t)
        {
          tmp = array[f];
          array[f] = array[i];
          array[i] = tmp ;
          f ++ ;
          equalnum ++ ;
        }
    } //end
    f--;
    if(equalnum > tk && (f - start + 1) == equalnum)
    {
      return t ;//這里是記錄數據相等的數目，當我們從開始start處到最后處end都被這個值給充斥了，那么肯定是這里面的值了，再進行下去就會陷入死循環了。
    }
    if(tk == (f - start + 1) )
    {
      return t ;
    }
    if((f - start + 1 ) > tk )
    {
      end = f ;
    }else
    {
       start = f + 1  ;
       tk = k - start  ; //這個地方犯過錯誤，就是寫成了k=k-start，在調試的時候老發現無限的循環。后來打印k的值的時候發現k的值都***為負了。這個bug，這個過錯使得在一次運行可能會得到正確的數據，但是多次運行后程序就崩潰。
     }
     len = end - start + 1 ;
     ps = rand()%len +start ;
  }
}
int main()
{
  int array[10] = {1,1,1,2,2,1,4,1,1,1};
  for(int i = 0 ; i < 10 ; i ++ )
  {
    cout<<findnumber(array,0,9,i+1)<<endl;
  }
  system("pause");
  return 0 ;
}

以上就是“怎么使用C++在無序數組中實現選擇第k小個數”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注創新互聯行業資訊頻道。

網頁題目：怎么使用C++在無序數組中實現選擇第k小個數-創新互聯
分享URL：http://vcdvsql.cn/article14/ddpode.html

成都網站建設公司_創新互聯，為您提供網頁設計公司、做網站、靜態網站、關鍵詞優化、App開發、ChatGPT

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯