用递归求数组最大值的位置

edussx 发表于 2013-2-10 19:43
要求输出结果是4，不是9

1. int max(const int a[], int n)
   
2. {
   
3.     if (n == 1)
   
4.         return n;
   
5.     int i = a[0];
   
6.     int next_index = max(a+1, n-1)+1;
   
7.     int j = a[next_index-1];
   
8.         printf("n=%d\n", n);
   
9.     printf("next_index=%d\n", next_index);
   
10.     printf("i=%d\n", i);
    
11.     printf("j=%d\n", j);
    
12.     printf("///////////////////////////////////////////\n");
    
13.     if (i > j)
    
14.         return 1;
    
15.     else
    
16.         return next_index;
    
17. }

复制代码

楼主看这样可以吗？不过返回的不是下标，是下标+1
比如:

1. index = max(a, 5);
   
2. value = a[index-1]

复制代码

rogerdai 发表于 2013-2-10 22:18
楼主看这样可以吗？不过返回的不是下标，是下标+1
比如:

其实我们的如出一辙哈~你的注释删了就差不多啦~思路是一样的~

我来贴个我的版本，不是很简洁呢

1. int max(const int a[],int n)
   
2. {
   
3.     if(n <= 1)
   
4.        return 0;
   
5.     int i,j,mid;
   
6.     mid = n/2;
   
7.     i = max(a,mid);
   
8.     j = max(a+mid+1,n-mid-1);
   
9.     if(a[i] < *(a+mid+1+j))
   
10.     {
    
11.        if(*(a+mid+1+j) < a[mid])
    
12.           return mid;
    
13.        else
    
14.           return j+mid+1;
    
15.     }
    
16.     else
    
17.     {
    
18.        if(a[i] < a[mid])
    
19.           return mid;
    
20.        else
    
21.           return i;
    
22.     }
    
23. }

复制代码

1、lz的思路已经很巧妙了，只要把返回值换回成数组的下标，注意比较时取数组值即可。
2、代码中还要加一个容错处理，就是当输入值n＜1时，（0或负数都可能），函数的返回值，或者做报错信号，或者兼容n=1处理。

学到很多，10楼的果然很简洁

1. int MaxIndex2(int* A,int n)
   
2. {
   
3.         if(n==1)
   
4.                 return 0;
   
5.         int mid=n/2;
   
6.         int left=MaxIndex(A,mid);
   
7.         int right=MaxIndex(A+mid,n-mid);
   
8.         return A[left] > A[right+mid]?left : right+mid;
   
9. }

复制代码

新人飘过，这个时间复杂度可以达到o(lgn)

LinRaise 发表于 2013-8-1 18:04
新人飘过，这个时间复杂度可以达到o(lgn)

这个复杂度是O(n)的吧，T(n)=2T(n/2)+O(1)，由主定理得O(n)
从另一方面想，从无序数组中找到最大值下标，至少需要把所有值都扫一遍啊，至少是O(n)

lvchaoshuai 发表于 2013-2-10 22:18
目测样例是有

这道题有很明显的函数式编程的风格啊, ocaml code:

1. let rec max l =
   
2.     match l with
   
3.     | [h] -> 0
   
4.     | h::t ->     
   
5.          let x = (max t) in                    
   
6.            if (h > (List.nth t x)) then 0
   
7.            else x+1;;
   

复制代码

int max(int a[], int low, int high){
    if(low<high-1){
         int mid = low + (high-low)/2;
         int lmax = max(a,low,mid);
         int hmax = max(a,mid+1,high);
         if(a[lmax]<a[hmax]) return hmax;
         else return lmax;
    }else if(low==high-1){
          if(a[low]<a[high]) return high;
          else return low;
    }else if(low==high){
           return low;
    }else{
          return -1;
   }
}
     

1. int max(const int a[], int n)
   
2. {
   
3.         if (n == 1) return 0;
   
4.     int n1 = max(a, n/2);
   
5.         int n2 = n/2 + max(a + n/2, n - n/2);
   
6.         return a[n1] > a[n2] ? n1:n2;
   
7. }

复制代码

lvchaoshuai大牛那样太优雅的代码一般不容易一眼看懂 我来个土一点的（其实是开始感觉二分速度会快点写完发现没区别。。。）