1から始まる配列インデックスを使用して変換アルゴリズム

Question

配列内でk番目に大きい番号を見つける再帰アルゴリズムの疑似コードがあります。擬似コードはインデックス1から始まる配列を使用しますが、コードを実際に記述するときはインデックス0から始まる配列が必要です。私はこれを行うアルゴリズムを調整する方法を把握することはできません。

Select-kth-Algorithm4(A: array [1…n] of n distinct integers; left, right, k: integers between 1 and n) 
pivotIndex = a randomly generated integer such that left≤pivotIndex≤right 
pivotNewIndex = partition(A, left, right, pivotIndex) 
if pivotNewIndex−left≥k then 
    return Select-kth-Algorithm4(A, left, pivotNewIndex−1, k) 
else if pivotNewIndex−left=k−1 then 
    return A[pivotNewIndex] 
else 
    return Select-kth-Algorithm4(A, pivotNewIndex+1, right, k−pivotNewIndex+left−1) 
//(Initial call to this algorithm should be Select-kth-Algorithm4(A,1, n, 5) for any particular value of n.} 

partition(A, left, right, pivotIndex) 
pivotValue = A[pivotIndex] 
swap A[pivotIndex] and A[right] 
storeIndex = left 
for i = left to (right−1) 
if A[i] > pivotValue then 
    swap A[storeIndex] and A[i] 
    storeIndex = storeIndex + 1 
swap A[right] and A[storeIndex] 
return storeIndex 

私はアルゴリズムに変更を加える必要はなく、最初の呼び出しだけであることを認識しています。しかし、私がそれをするとき、それは私に正しい価値を与えていません。それが問題であれば私の実際のコードです：

void Algorithm4(int *A, int left, int right, int k) { 
int pivotIndex = rand() % right + left; 
int pivotNewIndex = partition(A, left, right, pivotIndex); 
if(pivotNewIndex - left>= k) { 
    Algorithm4(A, left, pivotNewIndex-1, k);  
} 
else if(pivotNewIndex-left == k-1){ 
    cout<< A[pivotNewIndex]; 
} 
else { 
    Algorithm4(A, pivotNewIndex+1, right, k-pivotNewIndex+left-1); 
} 
} 
int partition(int *A, int left, int right, int pivotIndex) { 
int pivotValue = A[pivotIndex]; 
int temp = A[pivotIndex]; 
A[pivotIndex] = A[right]; 
A[right] = temp; 
int storeIndex = left; 
for(int i = left; i < right; i++) { 
    if(A[i] > pivotValue) { 
     int temp = A[storeIndex]; 
     A[storeIndex] = A[i]; 
     A[i] = temp; 
     storeIndex= storeIndex + 1; 
    } 
} 
temp = A[right]; 
A[right] = A[storeIndex]; 
A[storeIndex] = temp; 
return storeIndex; 
} 

Answer 1

何も変更する必要はありません。違いは、A、1、nの代わりにA、0、n-1で呼び出すという、この関数のルート呼び出しにあります。

理由は、最初の絶対または最後の要素がルート呼び出しでのみ使用されるためです。他の場所では、変数がその位置に使用されます。

以下

Answer 2

ちょうど私、1 vector.Youにおけるk番目の最大の要素は、私のプログラム.IN int[]にvector<int>&を変更する1 < = K < = N、N- vector.Forの簡単の大きさであることができます見つけるためのコードです配列の最初の要素を使用してパーティションを作成します。

int findKthLargest(vector<int>& nums, int k) {  
    const int m = nums.size(); 
    int l = 0; 
    int h = m - 1; 
    while(l <= h){ 
     int pivot = partition(l, h, nums); 
     if(pivot == m - k) return nums[pivot]; 
     if(pivot > m - k) h = pivot - 1; 
     else l = pivot + 1;   
    } 
} 
int partition(int l, int h, vector<int> &nums){ 
    int b = l; 
    int e = h; 
    int pivot = nums[l]; 
    while(b < e){ 
     while(b < e && nums[e] >= pivot) e--; 
     if(b < e){ 
      nums[b] = nums[e]; 
      b++; 
     } 

     while(b < e && nums[b] < pivot) b++; 
     if(b < e){ 
      nums[e] = nums[b]; 
      e--; 
     } 
    } 
    nums[b] = pivot; 
    return b; 
}