链接
https://leetcode-cn.com/problems/magic-index-lcci/
耗时
解题:40 min
题解:21 min
题意
魔术索引。 在数组A[0…n-1]中,有所谓的魔术索引,满足条件A[i] = i。给定一个有序整数数组,编写一种方法找出魔术索引,若有的话,在数组A中找出一个魔术索引,如果没有,则返回-1。若有多个魔术索引,返回索引值最小的一个。
思路
二分,并分三种情况考虑。
- nums[m] == m: 这时找到了一个可能的答案,记录下来,并令 t=m 向前寻找,因为要找到最小的索引,所以只需在前半部分里找即可
- nums[m] > m:出现这种情况时,最终答案可能在前半部分也可能在后半部分,我的想法是将 nums[s] 与 s 比较,如果相等则不用找了,就是这个,如果不相等 令 s=s+1 使得二分可以继续
- nums[m] < m:由于 nums[m] 可能是 负数,所以先判断是否是负数,如果是前半部分都是负数,不可能找到,所以直接 s=m+1;如果不是负数,那最终答案可能在前半部分也可能在后半部分,我的想法和之前一样,将 nums[s] 与 s 比较,如果相等则不用找了,就是这个,如果不相等 令 s=s+1 使得二分可以继续
时间复杂度:
O
(
l
o
g
n
)
O(logn)
O(logn),最坏
O
(
n
)
O(n)
O(n)
AC代码
class Solution {
public:
int findMagicIndex(vector<int>& nums) {
int n = nums.size();
int s = 0, t = n, ans = -1;
while(s < t) {
int m = s + ((t-s)>>1);
if(nums[m] == m) {
ans = m;
t = m;
}
else if(nums[m] > m) {
if(nums[s] != s) {
s += 1;
}
else {
ans = s;
break;
}
}
else if(nums[m] < m) {
if(nums[m] < 0) {
s = m+1;
}
else {
if(nums[s] != s) {
s += 1;
}
else {
ans = s;
break;
}
}
}
}
return ans;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)