【刷题之路】LeetCode 程序员面试金典 08.03. 魔术索引
一、题目描述
原题连接: 题目描述: 魔术索引。 在数组A[0…n-1]中,有所谓的魔术索引,满足条件A[i] = i。给定一个有序整数数组,编写一种方法找出魔术索引,若有的话,在数组A中找出一个魔术索引,如果没有,则返回-1。若有多个魔术索引,返回索引值最小的一个。
示例1:
输入: nums = [0, 2, 3, 4, 5] 输出: 0 说明: 0下标的元素为0
示例2:
输入: nums = [1, 1, 1] 输出: 1
说明: nums长度在[1, 1000000]之间 此题为原书中的 Follow-up,即数组中可能包含重复元素的版本
二、解题
1、方法1——暴力法
1.1、思路分析
最简单的方法就是直接遍历数组的每个元素,找到第一个nums[i] = i的元素,直接返回其下标即可。
1.2、代码实现
有了以上思路,那我们写起代码来也就水到渠成了:
int findMagicIndex1(int* nums, int numsSize) { assert(nums); int i = 0; for (i = 0; i < numsSize; i++) { if (nums[i] == i) { return i; } } return -1; }
时间复杂度:O(n),n为数组长度,最坏情况下我们需要遍历完数组中的所有元素。 空间复杂度:O(1),我们只需要用到常数级的额外空间。
2、方法2——二分+分治
2.1、思路分析
既然是在有序数组中进行查找,那我们很容易就能想到能使用二分查找,具体算法思路如下: 如果nums[mid] == mid,则说明如果想要找到更优解,就只能继续mid的左侧: 而当nums[mid] != mid时,并不能确定最优解是在左侧还是在右侧,因为左侧和右侧都有可能存在符合条件的解或者不存在解。所以我们这时候左侧右侧的区间都要寻找一遍: 所以在二分的基础上我们还需要使用分治算法的思想,来递归寻找左右两侧区间,只不过这里我们得有先寻找左侧区间, 如果在左区间找到了更优解,那就不需要再寻找右区间了。
2.2、代码实现
有了以上思路,那我们写起代码来也就水到渠成了:
// 先写一个二分分治算法 void binary_finder(int* nums, int left, int right, int* answer) { assert(nums && answer); if (left < right) { // 递归结束条件 return; } int mid = left + (right - left) / 2; if (nums[mid] == mid) { *answer = mid; return binary_finder(nums, left, mid - 1, answer); } else { return binary_finder(nums, left, mid - 1, answer); if (-1 == *answer || *answer > right) { return binary_finder(nums, mid + 1, right, answer); } } } int findMagicIndex2(int* nums, int numsSize) { assert(nums); int answer = -1; binary_finder(nums, 0, numsSize - 1, &answer); return answer; } int main() { int nums[] = { 3,4,5,5,5,5 }; int len = sizeof(nums) / sizeof(nums[0]); int result = findMagicIndex2(nums, len); printf("%d ", result); return 0; }
时间复杂度:O(n),n为数组的长度,最坏情况下,我们还是需要遍历完数组中的所有元素。 空间复杂度:O(n),空间复杂度主要取决于递归调用的次数,最坏的情况下我们每个元素都要判断一次,故需要调用n次,空间复杂度为O(n)。
上一篇:
Java基础知识总结(2021版)
下一篇:
几种常见的API接口分页方案