Microsoft : Find pivot

//Given a sorted array (ex. {1,2,3,4,5,6,7,8}). A random number from the array is taken and put the left side
//array to right side and left side array to right side.
//in the example; if 6 is randomly taken, the array will become like {7,8,6,1,2,3,4,5}

这题比较简单，程序写起来比较麻烦，考虑到相同值的情况

请问先将这个数列倒着排，然后再将pivot分开的两部分分别倒着排，可以吗？

回复 2# Imbalism
应该没错！如果给出的pivot是下标的话，三个reverse就能搞定

回复  Imbalism
应该没错！如果给出的pivot是下标的话，三个reverse就能搞定
darksteel 发表于 2011-5-8 22:22

    看标题，是Find Pivot, 不是转回来，可能题目没说清楚

回复  Imbalism
应该没错！如果给出的pivot是下标的话，三个reverse就能搞定
darksteel 发表于 2011-5-8 22:22

    不过如果题目是这样的话这个解法也很好啊

回复 4# wwwyhx
题目是略有点不清楚，是说给出原数组和新数组，让判断哪个元素是所选的pivot？

回复  wwwyhx
题目是略有点不清楚，是说给出原数组和新数组，让判断哪个元素是所选的pivot？
darksteel 发表于 2011-5-9 13:28

    没错

回复 7# wwwyhx
其实给出移动过的数组就行。
结果应该是返回值吧？因为如果是位置可能有多种情况。
大概是这样：

1. int FindPivot(int a[], int n)
   
2. {
   
3.         int i = 1;
   
4.         if(n == 1)
   
5.                 return a[0];
   
6.         while(a[i] == a[i-1])
   
7.                 i++;
   
8.         if(i == n || a[i] < a[i-1])
   
9.                 return a[i-1];
   
10.         while(a[i] >= a[i-1])
    
11.                 i++;
    
12.         return a[i];
    
13. }

复制代码

回复  wwwyhx
其实给出移动过的数组就行。
结果应该是返回值吧？因为如果是位置可能有多种情况。
大概是这样：
darksteel 发表于 2011-5-10 13:30

    服你了.... 二分都懒得用

回复 9# wwwyhx
好像真能用二分诶，不过边界条件比较多，想想就麻烦啊