Chinaunix首页 | 论坛 | 博客
  • 博客访问: 962384
  • 博文数量: 128
  • 博客积分: 10012
  • 博客等级: 上将
  • 技术积分: 2050
  • 用 户 组: 普通用户
  • 注册时间: 2008-10-15 17:49
文章分类

全部博文(128)

文章存档

2011年(16)

2009年(57)

2008年(55)

分类: C/C++

2008-11-01 20:35:08

问题:C++代码实现函数 FindSortedArrayRotation。该函数接受一个整数数组和数组的长度。这个整数数组本来是有序的(升序),但被轮转了X位置(对给定的整数X (0 <= X <= (arrayLength - 1)),数组的每个元素向前移动X位置,也就是array[i]移动到array[(i+X)%arrayLength]。请实现FindSortedArrayRotation,找出X。要求时间必须小于O(n) (面试大牛网)函数原型:int FindSortedArrayRotation(int *array, int arrayLength)。

英文原题:Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength - 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array. You should be able to do this in less than linear time.

 

参考代码:
以下为引用的内容:

int FindSortedArrayRotation(int *array, int arrayLength)

{

    // Insert your implementation here

  

    /* 

After rotation the array was divided into 2 parts: array[0…x-1] and array[x…arrayLength-1]. And each part is sorted in ascending order. But array[x-1]>array[x]. This is a turn corner. My idea is use binary_search algorithm to find the turn corner.

Running time is O(log(2)).

*/

 

int left = 0;

int right = arrayLength – 1;

if(array[left]<= array[right]) return 0;

while(left<=right)

{

int middle = (left+right)/2;

if(array[middle -1] > array[middle]) return middle;

if(array[middle] > array[right]) left = middle + 1;

else right = middle -1;

}

 

return -1;

 

}


阅读(1643) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~