[关闭]
@chyoo1991 2015-09-07T01:19:41.000000Z 字数 1512 阅读 1189

《剑指Offer》中取旋转数组最小数的学习

coding 旋转数组


见书66页。

O(logN)的算法核心观点在于把旋转数组看成两个递增子数组,运用二分查找算法实现。先考虑没有重复数字的情况,再考虑有重复的情况。

无重复数的代码[JAVA版]

  1. public class RolateArray {
  2. public static int getMinNum(int[] numbs) throws Exception{
  3. if(numbs == null || numbs.length == 0) throw new Exception("Invaid array!");
  4. int start = 0;
  5. int end = numbs.length - 1;
  6. int resultIndex = start; // 返回结果的下标默认为start,处理旋转度为0的情况
  7. while(numbs[start] >= numbs[end]) { //如果不满足这个条件,则原数组的旋转度为0
  8.  if(end - start == 1) { // start 一定在左边子序列中,end一定在右子序列中
  9.   resultIndex = end;
  10.   break;
  11.  }
  12.  int mid = (start + end) / 2;
  13.  if(numbs[mid] >= numbs[start]) //在左子序列
  14.   start = mid;
  15.  else if(numbs[mid] <= numbs[end]) // 在右子序列
  16.    end = mid;
  17. }
  18. return numbs[resultIndex];
  19. }
  20. public static void main(String[] args){
  21. int[] a1 = {3, 4, 5, 1, 2, 3}; // 可以求出来
  22. int[] a2 = {3, 3, 3, 1, 2, 3}; // 可以得到正确答案
  23. int[] a3 = {3, 4, 5, 1, 1, 2};
  24. try{
  25. System.out.println(getMinNum(a1));
  26. System.out.println(getMinNum(a2));
  27. System.out.println(getMinNum(a3));
  28. }catch(Exception e){
  29.    System.out.println(e);
  30. }
  31. }
  32. }

这个代码的问题在于有时候会因为重复数字而分错了组。当mid/start/end对应的值都相同的时候,这时候无法判断该往哪边移动。此时只能遍历了。

有重复版的代码

  1. public class RolateArray{
  2. public static int getMinNum(int[] numbs) throws Exception {
  3. if(numbs == null || numbs.length == 0) throw new Exception("Invalid array!");
  4. int start = 0;
  5. int end = numbs.length - 1;
  6. int resultIndex = start;
  7. while(numbs[start] >= numbs[end]) {
  8. if(end - start == 1) {
  9. resultIndex = end;
  10. break;
  11. }
  12. int mid (start + end) / 2;
  13. if(numbs[start] == numbs[end] && numbs[start] == numbs[mid]){
  14. int tmp = numbs[start];
  15. // 循环找出最小值
  16. for(int i = start + 1; i <= end; i++){
  17. if(numbs[i] < tmp)
  18. tmp = numbs[i];
  19. }
  20. return tmp;
  21. }
  22. else if(numbs[start] <= numbs[mid])
  23. //在左子序列中
  24. start = mid;
  25. else if(numbs[end] >= numbs[mid])
  26. //在右子序列中
  27. end = mid
  28. }
  29. return numbs[resultIndex];
  30. }
  31. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注