2

まず、私は C を初めて使用するので、私のアプローチは基本的なものです。ソートされた配列が回転されたポイントをチェックしようとしています。たとえば、(1 2 4 5 9) は (5 9 1 2 4) になります。配列を 2 つのサブ配列に「分割」して、[0] から開始して 1 つずつ増加するものと、[4] から開始して 1 ずつ減少するものをチェックしようとしています。これが私がこれまでに持っているものです：

#define size 5
int main(void)
{
int x, i, j, start, end;
int array1[size]= {4, 8, 0, 1, 3};
start = 0;
end = size -1;
while(start < end)
{
if (array1[start] < array1[end])
    start++;
    end--;

私が抱えている質問のいくつかは、私のアプローチが (外側から内側へ) 良いかどうか、または途中から始めて解決する必要があるかどうかです。また、ピボットが実際に発生する場所の決定をどのようにコーディングしますか。SO で C++ に関するいくつかの回答が表示されますが、C について明確な回答があまり見られないため、質問することにしました。アドバイスをいただければ幸いです。

4

2 に答える 2

2

問題を解決するのはかなり簡単です。元のセットはソートされているため、ヒットした要素が配列の最後の要素よりも小さくなるまで前方に繰り返します。これは元の最初の要素だったので、開始からの距離がR (mod N)に一致することがわかります。ここで、Rは回転距離、Nはsizeです。

int last = array[size - 1];
int r;
for (r = 0; array[r] >= last; ++r) ;
int pivot = array[r];
/* pivot was the original array[0] */
于 2012-09-15T07:05:14.347 に答える
1

C でピボット要素を見つけるためのコード

int findPivot(int arr[], int low, int high)
{
   // base cases
   if (high < low)  return -1;
   if (high == low) return low;

   int mid = (low + high)/2;   /*low + (high - low)/2;*/
   if (mid < high && arr[mid] > arr[mid + 1])
     return mid;
   if (mid > low && arr[mid] < arr[mid - 1])
     return (mid-1);
   if (arr[low] >= arr[mid])
     return findPivot(arr, low, mid-1);
   else
     return findPivot(arr, mid + 1, high);
}

配列が既にソートされている場合は -1 を返します。残りの部分は、バイナリ検索のように通常どおりです

于 2014-04-16T09:54:38.653 に答える