O（n）の長さnのソートされていない配列でk番目に大きい要素を見つける方法があると思います。または、おそらくそれは「期待される」O(n)か何かです。どうすればこれを行うことができますか？
238173 次
33 に答える
176
これは、 k次の統計量の検索と呼ばれます。平均時間と最悪の場合の時間をとる非常に単純なランダム化アルゴリズム（クイックセレクトと呼ばれる）と、最悪の場合の時間をとる非常に複雑な非ランダム化アルゴリズム（イントロセレクトと呼ばれる）があります。ウィキペディアにはいくつかの情報がありますが、あまり良くありません。O(n)O(n^2)O(n)
必要なものはすべて、これらのパワーポイントのスライドにあります。O(n)最悪の場合のアルゴリズム（イントロセレクト）の基本的なアルゴリズムを抽出するだけです。
Select(A,n,i):
Divide input into ⌈n/5⌉ groups of size 5.
/* Partition on median-of-medians */
medians = array of each group’s median.
pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
Left Array L and Right Array G = partition(A, pivot)
/* Find ith element in L, pivot, or G */
k = |L| + 1
If i = k, return pivot
If i < k, return Select(L, k-1, i)
If i > k, return Select(G, n-k, i-k)
また、CormenetalによるIntroductiontoAlgorithmsの本でも非常に詳しく説明されています。
于 2008-10-30T21:48:05.517 に答える
121
O(n)またはそのようなものとは対照的に、真のアルゴリズムO(kn)が必要な場合は、クイック選択を使用する必要があります（基本的に、興味のないパーティションを捨てるクイックソートです）。私の教授は、ランタイム分析を含む素晴らしい記事を書いています: (参照)
QuickSelect アルゴリズムは、並べ替えられていない要素の配列から k 番目に小さい要素をすばやく見つけnます。これはRandomizedAlgorithmであるため、最悪の場合の予想実行時間を計算します。
これがアルゴリズムです。
QuickSelect(A, k)
let r be chosen uniformly at random in the range 1 to length(A)
let pivot = A[r]
let A1, A2 be new arrays
# split into a pile A1 of small elements and A2 of big elements
for i = 1 to n
if A[i] < pivot then
append A[i] to A1
else if A[i] > pivot then
append A[i] to A2
else
# do nothing
end for
if k <= length(A1):
# it's in the pile of small elements
return QuickSelect(A1, k)
else if k > length(A) - length(A2)
# it's in the pile of big elements
return QuickSelect(A2, k - (length(A) - length(A2))
else
# it's equal to the pivot
return pivot
このアルゴリズムの実行時間は? 敵が私たちのためにコインを投げた場合、ピボットが常に最大の要素であり、k常に 1 であることがわかり、実行時間が次のようになります。
T(n) = Theta(n) + T(n-1) = Theta(n2)しかし、選択肢が実際にランダムである場合、予想実行時間は次の式で与えられます。
T(n) <= Theta(n) + (1/n) ∑<sub>i=1 to nT(max(i, n-i-1))ここで、再帰は常にA1またはの大きい方に到達するという完全に合理的ではない仮定を行っていA2ます。
T(n) <= anいくつか推測してみましょうa。次に、取得します
T(n)
<= cn + (1/n) ∑<sub>i=1 to nT(max(i-1, n-i))
= cn + (1/n) ∑<sub>i=1 to floor(n/2) T(n-i) + (1/n) ∑<sub>i=floor(n/2)+1 to n T(i)
<= cn + 2 (1/n) ∑<sub>i=floor(n/2) to n T(i)
<= cn + 2 (1/n) ∑<sub>i=floor(n/2) to n aiそして今、どういうわけか、プラス記号の右側にある恐ろしい合計を取得してcn、左側のを吸収する必要があります。としてバインドすると2(1/n) ∑<sub>i=n/2 to n an、おおよそ になり2(1/n)(n/2)an = anます。しかし、これは大きすぎます - 余分に詰め込む余地がありませんcn。それでは、算術級数の公式を使用して合計を展開しましょう。
∑<sub>i=floor(n/2) to n i
= ∑<sub>i=1 to n i - ∑<sub>i=1 to floor(n/2) i
= n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2
<= n2/2 - (n/4)2/2
= (15/32)n2ここで、 n が「十分に大きい」ことを利用して、醜いfloor(n/2)要素をよりクリーンな (そして小さい) 要素に置き換えn/4ます。これで、続行できます
cn + 2 (1/n) ∑<sub>i=floor(n/2) to n ai,
<= cn + (2a/n) (15/32) n2
= n (c + (15/16)a)
<= an提供されa > 16cます。
これにより が得られT(n) = O(n)ます。明らかOmega(n)に であるため、 が得られT(n) = Theta(n)ます。
于 2008-10-31T22:23:11.870 に答える
15
その（「k番目に大きい要素配列」）に関する簡単なGoogleはこれを返しました：http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17
"Make one pass through tracking the three largest values so far."
（それは特に3D最大のものでした）
そしてこの答え：
Build a heap/priority queue. O(n)
Pop top element. O(log n)
Pop top element. O(log n)
Pop top element. O(log n)
Total = O(n) + 3 O(log n) = O(n)
于 2008-10-30T21:12:11.690 に答える
11
あなたはクイックソートが好きです。ランダムに要素を選び、すべてを高くまたは低く押します。この時点で、実際に選択した要素がわかります。それが完了したk番目の要素である場合は、k番目の要素が含まれるビン（高いまたは低い）で繰り返します。統計的に言えば、時間k番目の要素がn、O（n）とともに成長することを見つけるのに必要です。
于 2010-06-23T02:14:15.787 に答える
6
A Programmer's Companion to Algorithm Analysisでは、O(n)のバージョンが提供されていますが、著者は定数係数が非常に高いと述べているため、単純な sort-the-list-then-select メソッドを使用することをお勧めします。
私はあなたの質問の手紙に答えました:)
于 2008-10-30T21:17:23.210 に答える
5
C++ 標準ライブラリには、データを変更しますが、ほぼ正確にその関数呼び出しがあります。nth_element線形実行時間 O(N) を想定しており、部分的な並べ替えも行います。
const int N = ...;
double a[N];
// ...
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a
于 2008-10-30T22:53:51.923 に答える
4
動的計画法、特にトーナメント法を使用して、n個のソートされていない要素でk番目の最小値を見つけることを実装しました。実行時間はO（n + klog（n））です。使用されるメカニズムは、選択アルゴリズムに関するWikipediaページのメソッドの1つとしてリストされています（上記の投稿の1つに示されています）。アルゴリズムについて読むことができ、私のブログページFinding KthMinimumでコード（java）を見つけることもできます。さらに、ロジックはリストの半順序を実行できます-O（klog（n））時間で最初のK min（またはmax）を返します。
コードは結果のk番目の最小値を提供しましたが、トーナメントツリーを作成するために行われた事前作業を無視して、O（klog（n））でk番目の最大値を見つけるために同様のロジックを使用できます。
于 2011-01-04T05:43:15.603 に答える
4
O（n）の複雑さについてはよくわかりませんが、O（n）とnLog（n）の間にあることは間違いありません。また、nLog（n）よりもO（n）に近いことを確認してください。関数はJavaで書かれています
public int quickSelect(ArrayList<Integer>list, int nthSmallest){
//Choose random number in range of 0 to array length
Random random = new Random();
//This will give random number which is not greater than length - 1
int pivotIndex = random.nextInt(list.size() - 1);
int pivot = list.get(pivotIndex);
ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();
//Split list into two.
//Value smaller than pivot should go to smallerNumberList
//Value greater than pivot should go to greaterNumberList
//Do nothing for value which is equal to pivot
for(int i=0; i<list.size(); i++){
if(list.get(i)<pivot){
smallerNumberList.add(list.get(i));
}
else if(list.get(i)>pivot){
greaterNumberList.add(list.get(i));
}
else{
//Do nothing
}
}
//If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list
if(nthSmallest < smallerNumberList.size()){
return quickSelect(smallerNumberList, nthSmallest);
}
//If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
//The step is bit tricky. If confusing, please see the above loop once again for clarification.
else if(nthSmallest > (list.size() - greaterNumberList.size())){
//nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in
//smallerNumberList
nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
return quickSelect(greaterNumberList,nthSmallest);
}
else{
return pivot;
}
}
于 2011-08-18T07:25:06.610 に答える
3
Python でのセクシーなクイック選択
def quickselect(arr, k):
'''
k = 1 returns first element in ascending order.
can be easily modified to return first element in descending order
'''
r = random.randrange(0, len(arr))
a1 = [i for i in arr if i < arr[r]] '''partition'''
a2 = [i for i in arr if i > arr[r]]
if k <= len(a1):
return quickselect(a1, k)
elif k > len(arr)-len(a2):
return quickselect(a2, k - (len(arr) - len(a2)))
else:
return arr[r]
于 2014-07-22T16:52:28.497 に答える
3
O(n + kn) = O(n) (定数 k の場合) は時間、O(k) は空間で、これまでに見た k 個の最大要素を追跡することで実行できます。
配列内の各要素について、最大の k 個のリストをスキャンし、最小の要素が大きい場合は新しい要素に置き換えることができます。
ただし、Warren の優先ヒープ ソリューションの方が優れています。
于 2008-10-30T21:17:49.777 に答える
2
線形時間で配列の中央値を見つけ、クイックソートとまったく同じように分割手順を使用して、配列を2つの部分に分割します。中央値の左側の値は中央値よりも小さく（<）、右側の値は中央値よりも大きくなります（>） 、これも線形時間で実行できます。次に、k番目の要素が存在する配列のその部分に移動します。ここで、繰り返しは次のようになります。T（n）= T（n / 2）+ cnこれにより、O（n）全体が得られます。
于 2010-04-18T18:21:39.587 に答える
2
以下は完全な実装へのリンクで、ソートされていないアルゴリズムで K 番目の要素を見つけるアルゴリズムがどのように機能するかについて非常に広範な説明があります。基本的な考え方は、QuickSort のように配列を分割することです。ただし、極端なケース (たとえば、すべてのステップで最小の要素がピボットとして選択され、アルゴリズムが O(n^2) 実行時間に縮退する場合) を回避するために、中央値アルゴリズムと呼ばれる特別なピボット選択が適用されます。ソリューション全体は、最悪の場合でも平均的な場合でも O(n) 時間で実行されます。
記事全文へのリンクは次のとおりです (これは K 番目に小さい要素を見つけることに関するものですが、K 番目に大きい要素を見つけるための原則は同じです)。
于 2013-07-19T09:17:41.933 に答える
2
こういうアプローチはいかがですか
buffer of length kaと aを維持し、tmp_maxtmp_max を取得すると O(k) になり、n 回実行されるので、次のようになります。O(kn)
それは正しいですか、それとも何か不足していますか?
クイックセレクトの平均的なケースとメディアン統計法の最悪のケースに勝るものはありませんが、理解と実装は非常に簡単です。
于 2016-06-16T09:55:13.347 に答える
1
リストを繰り返します。現在の値が保存されている最大値よりも大きい場合は、それを最大値として保存し、1 ～ 4 を下げて 5 をリストから外します。そうでない場合は、2 と比較して同じことを行います。5 つの格納された値すべてに対してチェックを繰り返します。これはO（n）でそれを行う必要があります
于 2008-10-30T21:10:13.583 に答える
1
これは、Randomized QuickSelect の C++ 実装です。アイデアは、ピボット要素をランダムに選択することです。ランダム化されたパーティションを実装するには、ランダム関数 rand() を使用して l と r の間のインデックスを生成し、ランダムに生成されたインデックスの要素を最後の要素と交換し、最後に最後の要素をピボットとして使用する標準のパーティション プロセスを呼び出します。
#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;
int randomPartition(int arr[], int l, int r);
// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around a random element and
// get position of pivot element in sorted array
int pos = randomPartition(arr, l, r);
// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return kthSmallest(arr, l, pos-1, k);
// Else recur for right subarray
return kthSmallest(arr, pos+1, r, k-pos+l-1);
}
// If k is more than number of elements in array
return INT_MAX;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// Standard partition process of QuickSort(). It considers the last
// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x) //arr[i] is bigger than arr[j] so swap them
{
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[r]); // swap the pivot
return i;
}
// Picks a random pivot element between l and r and partitions
// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
int n = r-l+1;
int pivot = rand() % n;
swap(&arr[l + pivot], &arr[r]);
return partition(arr, l, r);
}
// Driver program to test above methods
int main()
{
int arr[] = {12, 3, 5, 7, 4, 19, 26};
int n = sizeof(arr)/sizeof(arr[0]), k = 3;
cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
return 0;
}
上記のソリューションの最悪の場合の時間計算量は依然として O(n2) です。最悪の場合、ランダム化された関数は常にコーナー要素を選択する可能性があります。上記のランダム化された QuickSelect の予想される時間の複雑さは Θ(n) です
于 2015-04-19T11:47:20.393 に答える
1
Haskell ソリューション:
kthElem index list = sort list !! index
withShape ~[] [] = []
withShape ~(x:xs) (y:ys) = x : withShape xs ys
sort [] = []
sort (x:xs) = (sort ls `withShape` ls) ++ [x] ++ (sort rs `withShape` rs)
where
ls = filter (< x)
rs = filter (>= x)
これは、 withShape メソッドを使用して実際に計算せずにパーティションのサイズを検出することにより、中央値解の中央値を実装します。
于 2015-01-23T23:42:31.793 に答える
1
n から k 番目に大きい整数を見つけるための median - of - medians アルゴリズムの説明は、ここにあります: http://cs.indstate.edu/~spitla/presentation.pdf
C++ での実装は以下のとおりです。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMedian(vector<int> vec){
// Find median of a vector
int median;
size_t size = vec.size();
median = vec[(size/2)];
return median;
}
int findMedianOfMedians(vector<vector<int> > values){
vector<int> medians;
for (int i = 0; i < values.size(); i++) {
int m = findMedian(values[i]);
medians.push_back(m);
}
return findMedian(medians);
}
void selectionByMedianOfMedians(const vector<int> values, int k){
// Divide the list into n/5 lists of 5 elements each
vector<vector<int> > vec2D;
int count = 0;
while (count != values.size()) {
int countRow = 0;
vector<int> row;
while ((countRow < 5) && (count < values.size())) {
row.push_back(values[count]);
count++;
countRow++;
}
vec2D.push_back(row);
}
cout<<endl<<endl<<"Printing 2D vector : "<<endl;
for (int i = 0; i < vec2D.size(); i++) {
for (int j = 0; j < vec2D[i].size(); j++) {
cout<<vec2D[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
// Calculating a new pivot for making splits
int m = findMedianOfMedians(vec2D);
cout<<"Median of medians is : "<<m<<endl;
// Partition the list into unique elements larger than 'm' (call this sublist L1) and
// those smaller them 'm' (call this sublist L2)
vector<int> L1, L2;
for (int i = 0; i < vec2D.size(); i++) {
for (int j = 0; j < vec2D[i].size(); j++) {
if (vec2D[i][j] > m) {
L1.push_back(vec2D[i][j]);
}else if (vec2D[i][j] < m){
L2.push_back(vec2D[i][j]);
}
}
}
// Checking the splits as per the new pivot 'm'
cout<<endl<<"Printing L1 : "<<endl;
for (int i = 0; i < L1.size(); i++) {
cout<<L1[i]<<" ";
}
cout<<endl<<endl<<"Printing L2 : "<<endl;
for (int i = 0; i < L2.size(); i++) {
cout<<L2[i]<<" ";
}
// Recursive calls
if ((k - 1) == L1.size()) {
cout<<endl<<endl<<"Answer :"<<m;
}else if (k <= L1.size()) {
return selectionByMedianOfMedians(L1, k);
}else if (k > (L1.size() + 1)){
return selectionByMedianOfMedians(L2, k-((int)L1.size())-1);
}
}
int main()
{
int values[] = {2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
vector<int> vec(values, values + 25);
cout<<"The given array is : "<<endl;
for (int i = 0; i < vec.size(); i++) {
cout<<vec[i]<<" ";
}
selectionByMedianOfMedians(vec, 8);
return 0;
}
于 2013-02-28T19:50:18.780 に答える
1
1つの答えを提案したい
最初の k 個の要素を取り、それらを k 個の値のリンクされたリストに並べ替える場合
最悪の場合でも残りの nk 値の挿入ソートを行う場合、他のすべての値について、最悪の場合でも比較の数は k*(nk) になり、ソートされる前の k 値の場合は k*(k- 1) したがって、o(n) である (nk-k) となります。
乾杯
于 2009-07-31T16:51:47.017 に答える
1
QuickSelect よりも実装が簡単なWirth の選択アルゴリズムもあります。Wirth の選択アルゴリズムは QuickSelect よりも低速ですが、いくつかの改良により高速になりました。
さらに詳細に。Vladimir Zabrodsky の MODIFIND 最適化と 3 の中央値のピボット選択を使用し、アルゴリズムのパーティショニング部分の最終ステップに注意を払って、次のアルゴリズムを思いつきました (「LefSelect」という名前が想像できます)。
#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }
# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
int l=0, m = n-1, i=l, j=m;
float x;
while (l<m) {
if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
if( a[j] < a[k] ) F_SWAP(a[k],a[j]);
x=a[k];
while (j>k & i<k) {
do i++; while (a[i]<x);
do j--; while (a[j]>x);
F_SWAP(a[i],a[j]);
}
i++; j--;
if (j<k) {
while (a[i]<x) i++;
l=i; j=m;
}
if (k<i) {
while (x<a[j]) j--;
m=j; i=l;
}
}
return a[k];
}
ここで行ったベンチマークでは、LefSelect は QuickSelect よりも 20 ～ 30% 高速です。
于 2014-11-03T23:15:27.967 に答える
0
eladv が提案したアルゴリズムの実装を次に示します (ランダム ピボットを使用した実装もここに示します)。
public class Median {
public static void main(String[] s) {
int[] test = {4,18,20,3,7,13,5,8,2,1,15,17,25,30,16};
System.out.println(selectK(test,8));
/*
int n = 100000000;
int[] test = new int[n];
for(int i=0; i<test.length; i++)
test[i] = (int)(Math.random()*test.length);
long start = System.currentTimeMillis();
random_selectK(test, test.length/2);
long end = System.currentTimeMillis();
System.out.println(end - start);
*/
}
public static int random_selectK(int[] a, int k) {
if(a.length <= 1)
return a[0];
int r = (int)(Math.random() * a.length);
int p = a[r];
int small = 0, equal = 0, big = 0;
for(int i=0; i<a.length; i++) {
if(a[i] < p) small++;
else if(a[i] == p) equal++;
else if(a[i] > p) big++;
}
if(k <= small) {
int[] temp = new int[small];
for(int i=0, j=0; i<a.length; i++)
if(a[i] < p)
temp[j++] = a[i];
return random_selectK(temp, k);
}
else if (k <= small+equal)
return p;
else {
int[] temp = new int[big];
for(int i=0, j=0; i<a.length; i++)
if(a[i] > p)
temp[j++] = a[i];
return random_selectK(temp,k-small-equal);
}
}
public static int selectK(int[] a, int k) {
if(a.length <= 5) {
Arrays.sort(a);
return a[k-1];
}
int p = median_of_medians(a);
int small = 0, equal = 0, big = 0;
for(int i=0; i<a.length; i++) {
if(a[i] < p) small++;
else if(a[i] == p) equal++;
else if(a[i] > p) big++;
}
if(k <= small) {
int[] temp = new int[small];
for(int i=0, j=0; i<a.length; i++)
if(a[i] < p)
temp[j++] = a[i];
return selectK(temp, k);
}
else if (k <= small+equal)
return p;
else {
int[] temp = new int[big];
for(int i=0, j=0; i<a.length; i++)
if(a[i] > p)
temp[j++] = a[i];
return selectK(temp,k-small-equal);
}
}
private static int median_of_medians(int[] a) {
int[] b = new int[a.length/5];
int[] temp = new int[5];
for(int i=0; i<b.length; i++) {
for(int j=0; j<5; j++)
temp[j] = a[5*i + j];
Arrays.sort(temp);
b[i] = temp[2];
}
return selectK(b, b.length/2 + 1);
}
}
于 2016-06-02T09:05:39.030 に答える
0
このリンクの最後に移動します: ...........
于 2016-07-25T17:03:47.067 に答える
0
私はこのアルゴリズムを思いつき、O（n）のようです：
k=3 としましょう。配列内で 3 番目に大きい項目を見つけたいとします。3 つの変数を作成し、配列の各項目をこれら 3 つの変数の最小値と比較します。配列アイテムが最小値より大きい場合、最小変数をアイテム値に置き換えます。配列の最後まで同じことを続けます。3 つの変数の最小値は、配列内で 3 番目に大きい項目です。
define variables a=0, b=0, c=0
iterate through the array items
find minimum a,b,c
if item > min then replace the min variable with item value
continue until end of array
the minimum of a,b,c is our answer
そして、K 番目に大きいアイテムを見つけるには、K 個の変数が必要です。
例: (k=3)
[1,2,4,1,7,3,9,5,6,2,9,8]
Final variable values:
a=7 (answer)
b=8
c=9
誰かがこれを見直して、私が欠けているものを教えてもらえますか?
于 2015-08-06T17:23:24.187 に答える
-1
私がすることはこれです：
initialize empty doubly linked list l
for each element e in array
if e larger than head(l)
make e the new head of l
if size(l) > k
remove last element from l
the last element of l should now be the kth largest element
リンクリストの最初と最後の要素へのポインタを保存するだけです。これらは、リストが更新されたときにのみ変更されます。
アップデート：
initialize empty sorted tree l
for each element e in array
if e between head(l) and tail(l)
insert e into l // O(log k)
if size(l) > k
remove last element from l
the last element of l should now be the kth largest element
于 2008-10-30T21:19:00.757 に答える
-1
最初に、O(n) 時間かかるソートされていない配列から BST を構築できます。BST から、O(n) の順序でカウントされる O(log(n)) 内の k 番目に小さい要素を見つけることができます。
于 2013-09-17T11:30:12.817 に答える
-2
k の値が非常に小さい場合 (つまり、k << n の場合)、~O(n) 時間で完了できます。それ以外の場合、k が n に匹敵する場合、O(nlogn) で取得します。
于 2012-10-05T05:21:15.823 に答える