论坛 › C\C++交流 › 搜索旋转排序数列

addendum777 发表于 2022-10-11 17:41:16

搜索旋转排序数列

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!='\0';i++)
    {
      lens++;
    }

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

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


}哪里出现了问题

jhq999 发表于 2022-10-11 21:21:14

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

jhq999 发表于 2022-10-12 11:40:54

本帖最后由 jhq999 于 2022-10-12 11:54 编辑

#include<stdio.h>

int search(int num[],int n,int target)
{
    int i=0,j=n-1,k=0;
    while(num>num)
    {
      k=(i+j)/2;
      if(num>num)i=k;
      else j=k;

    }////先折半查找出最大,也就是分界线

    if(target>=num)i=0,j=k;
    else if(target<=num)i=k+1,j=n-1;////判断target在那个段里

    while(i<j-1)//////////再在这个段里折半查找
    {
      k=(i+j)/2;
      if(target>num)i=k;
      else j=k;

    }
    if(target==num)return i;
    else if(target==num)return j;
    return -1;
}
int main()
{
    int num[]={3,4,5,6,7,9,16,0,1};
    printf("%d",search(num,9,16));
    return 0;
}

傻眼貓咪 发表于 2022-10-12 13:18:58

#include <stdio.h>

int foo(int nums[], int size, int target) {
        if (target < nums) {
                for (int i = size - 1; ; --i) {
                        if (nums == target) {
                                return i;
                        }
                        if (nums < nums) {
                                break;
                        }
                }
        }
        else {
                for (int i = 0; ; ++i) {
                        if (nums == target) {
                                return i;
                        }
                        if (nums > nums) {
                                break;
                        }
                }
        }
        return -1;
}

int main(void) {
        int nums[] = { 4, 5, 6, 7, 0, 1, 2};
        printf("%d", foo(nums, 7, 0));

        return 0;
}

ExiaGN001 发表于 2022-10-14 22:05:53

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

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

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

查看完整版本: 搜索旋转排序数列