搜索旋转排序数列

addendum777

int search(int* nums, int numsSize, int target){
    int i,j;
    int lens=0;
    int * result=(int *)malloc(sizeof(int)*numsSize);
    for(i=0;nums[i]!='\0';i++)
    {
        lens++;
    }

    if(target>lens)
    return -1;//不存在这个目标值

    for(i=target,j=0;i<numsSize-1;i++,j++)
    {
        result[j]=nums[i];
    }
    for(i=0,j=(numsSize-target);i<target;i++)
    {
        result[j]=nums;
    }
    return result[target];


}哪里出现了问题[/i][/i]

jhq999

看来语文不好，才看明白什么意思，就是把本来有序的数组在某处被旋转了，让你以最小的复杂度来判断在否存在，存在给出下标

jhq999

1. #include<stdio.h>
   
2. 
   
3. int search(int num[],int n,int target)
   
4. {
   
5.     int i=0,j=n-1,k=0;
   
6.     while(num[i]>num[j])
   
7.     {
   
8.         k=(i+j)/2;
   
9.         if(num[k]>num[i])i=k;
   
10.         else j=k;
    
11. 
    
12.     }////先折半查找出最大,也就是分界线
    
13. 
    
14.     if(target>=num[0])i=0,j=k;
    
15.     else if(target<=num[n-1])i=k+1,j=n-1;////判断target在那个段里
    
16. 
    
17.     while(i<j-1)//////////再在这个段里折半查找
    
18.     {
    
19.         k=(i+j)/2;
    
20.         if(target>num[k])i=k;
    
21.         else j=k;
    
22. 
    
23.     }
    
24.     if(target==num[i])return i;
    
25.     else if(target==num[j])return j;
    
26.     return -1;
    
27. }
    
28. int main()
    
29. {
    
30.     int num[]={3,4,5,6,7,9,16,0,1};
    
31.     printf("%d",search(num,9,16));
    
32.     return 0;
    
33. }

复制代码

傻眼貓咪

1. #include <stdio.h>
   
2. 
   
3. int foo(int nums[], int size, int target) {
   
4.         if (target < nums[0]) {
   
5.                 for (int i = size - 1; ; --i) {
   
6.                         if (nums[i] == target) {
   
7.                                 return i;
   
8.                         }
   
9.                         if (nums[i] < nums[i - 1]) {
   
10.                                 break;
    
11.                         }
    
12.                 }
    
13.         }
    
14.         else {
    
15.                 for (int i = 0; ; ++i) {
    
16.                         if (nums[i] == target) {
    
17.                                 return i;
    
18.                         }
    
19.                         if (nums[i] > nums[i + 1]) {
    
20.                                 break;
    
21.                         }
    
22.                 }
    
23.         }
    
24.         return -1;
    
25. }
    
26. 
    
27. int main(void) {
    
28.         int nums[] = { 4, 5, 6, 7, 0, 1, 2};
    
29.         printf("%d", foo(nums, 7, 0));
    
30. 
    
31.         return 0;
    
32. }

复制代码

ExiaGN001

这道题全部时间复杂度下限是o(n)

两种做法：
1、
o(n)读数据
o(n* log2 n)快排 或 o(n)基数排序
o(log2 n)二分查找

2.
o(n)读数据
o(n)直接查找