门户网站和社交网络的区别,平面设计师要学哪些软件,如何做单位网站,wordpress生成标签页目录 题目
思路
代码
暴力解法
分方向法
二分法 题目
整数数组 nums 按升序排列#xff0c;数组中的值 互不相同 。
在传递给函数之前#xff0c;nums 在预先未知的某个下标 k#xff08;0 k nums.length#xff09;上进行了 旋转#xff0c;使数组变为 …目录 题目
思路
代码
暴力解法
分方向法
二分法 题目
整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标 从 0 开始 计数。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1
输入nums [4,5,6,7,0,1,2], target 0
输出4示例 2
输入nums [4,5,6,7,0,1,2], target 3
输出-1
示例 3
输入nums [1], target 0
输出-1提示
1 nums.length 5000-104 nums[i] 104nums 中的每个值都 独一无二题目数据保证 nums 在预先未知的某个下标上进行了旋转-104 target 104 思路
不考虑要求时间复杂度为 O(log n) 的算法的话
可以暴力解法直接从开始往后遍历。也可以先比较nums[ 0 ]判断是否与target相等相等就直接返回0如果大于target则从后往前遍历否则从前往后遍历。
考虑时间复杂度可以利用二分法查找。
代码
暴力解法
int search(int* nums, int numsSize, int target)
{int i;for(i 0; i numsSize; i ){if(nums[i] target){return i;}}return -1;
}我只不过不 李姐 理解为什么暴力解法的数据不算差。
分方向法
int search(int* nums, int numsSize, int target)
{if(nums[0]target){int i;for(i0;inumsSizetargetnums[i];i);if(targetnums[i]inumsSize){return i;}}else if(nums[0]target){int i;for( inumsSize-1;i0targetnums[i];i--);if(targetnums[i]i0){return i;} }else return 0;return -1;
} 二分法
#includestdio.h
#includestdlib.hint dichsearch(int nums[],int low,int high,int target);
int search(int* nums, int numsSize, int target);int main()
{int nums[7]{4,5,6,7,0,1,2};printf(%d,search(nums,7,0));
}int search(int* nums, int numsSize, int target)
{int t;for(t0;tnumsSize-1nums[t]nums[t1];t);if(nums[0]target){return dichsearch(nums,0,t,target);}else if(nums[0]target){return dichsearch(nums,t1,numsSize-1,target);}else return 0;
}int dichsearch(int nums[],int low,int high,int target)
{while(lowhigh){int mid(lowhigh)/2;if(nums[mid]target)lowmid1;else if(nums[mid]target)highmid-1;else return mid;}return -1;
}
