b******y
发帖数: 126 | 1 A sorted array is rotated(rotate position is unknown), find the index for
the smallest element.
Example: 1 2 3 4 5 6 7, after rotated to the right becomes 4 5 6 7 1 2 3 | a*****y
发帖数: 467 | 2 每次比较中间和两头的值吧
跟rotated array的二分查找类似
【在 b******y 的大作中提到】
: A sorted array is rotated(rotate position is unknown), find the index for
: the smallest element.
: Example: 1 2 3 4 5 6 7, after rotated to the right becomes 4 5 6 7 1 2 3
| B*****g
发帖数: 193 | 3 怎么知道中间？
One stupid algorithm I can think of:
int smallestIndex(int arr[], int size)
{
int smallest = arr[0];
int index = 0;
for( int i = 1; i < size; ++i ){
if( arr[i] < arr[i-1] && smallest > arr[i] ){
smallest = arr[i];
index = i;
}
}
return index;
}
【在 a*****y 的大作中提到】
: 每次比较中间和两头的值吧
: 跟rotated array的二分查找类似
| c**********e
发帖数: 2007 | 4 The trick of the question is that, in the worst scenario, the approach can
only be O(n). If the array has all a[i]=1, you have to go through every
element. If you do not, one of it (if only one of it) could be 0. But for
general case, it should be O(logn) (the binary search approach).
With that the approach is clear. Use recursion. For an array a[i] to a[j]
with i
)/2 or k=(i+j+1)/2. If a[k]>a[j], then call the subroutine for
【在 b******y 的大作中提到】
: A sorted array is rotated(rotate position is unknown), find the index for
: the smallest element.
: Example: 1 2 3 4 5 6 7, after rotated to the right becomes 4 5 6 7 1 2 3
| w******y
发帖数: 519 | |
|
