网站用的什么数据库,免费游戏网站制作,拓者室内设计网站,成都定制小程序开发公司1 题目
整数数组 nums 按升序排列#xff0c;数组中的值 互不相同 。
在传递给函数之前#xff0c;nums 在预先未知的某个下标 k#xff08;0 k nums.length#xff09;上进行了 旋转#xff0c;使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], num…1 题目
整数数组 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) 的解决方案吗
2 思路
题目要求时间复杂度为 O(log n), 那么就需要用二分法的方法来. 虽然整个序列并不是有序的, 但是二分之后必然有一边是有序的, 所以二分之后检查目标是否在有序的一边, 并重新确定左右边界, 循环下去.
代码: int search(vectorint nums, int target) {int res_index -1;int nums_size nums.size();if (nums_size 0) {int left_idx 0;int right_idx nums_size - 1;while (left_idx right_idx) {if (nums[left_idx] target)return left_idx;if (nums[right_idx] target)return right_idx;int check_index (left_idx right_idx) / 2;if (nums[check_index] target)return check_index;bool left_inorder nums[left_idx] nums[check_index];bool target_in_inorder left_inorder ?(target nums[check_index] target nums[left_idx]) :(target nums[right_idx] target nums[check_index 1]);if (target_in_inorder) {left_idx left_inorder ? left_idx : check_index 1;right_idx left_inorder ? check_index : right_idx;} else {left_idx left_inorder ? check_index 1 : left_idx;right_idx left_inorder ? right_idx : check_index;}}if (nums[left_idx] target)return left_idx;}return res_index;}
