2

首先让我说我是 C 新手，所以我的方法是基本的。我正在尝试检查排序数组的旋转点。例如 (1 2 4 5 9) 变为 (5 9 1 2 4)。我试图将数组“拆分”为两个子数组，并检查一个从 [0] 开始并增加一，从 [4] 开始并减少一。这是我到目前为止所拥有的：

#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 回答