这是悦乐书的第 297 次更新, 第 316 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 165 题 (顺位题号是 704). 给定 n 个元素的排序(按升序) 整数数组 nums 和目标值, 编写一个函数来搜索 nums 中的目标. 如果 target 存在, 则返回其索引, 否则返回 - 1. 例如:
输入: nums = [-1,0,3,5,9,12], 目标 = 9
输出: 4
说明: 9 存在于 nums 中, 其索引为 4
输入: nums = [-1,0,3,5,9,12],target = 2
输出:-1
说明: 2 在 nums 中不存在, 因此返回 - 1
注意:
nums 中的所有元素都是唯一的.
n 将在 [1,10000] 范围内.
nums 中每个元素的值将在 [-9999,9999] 范围内.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
使用二分查找. 取数组的第一位和最后一位索引值, 计算取出中间数做新索引, 判断新索引对应的元素是否等于目标值, 等于就直接返回新索引, 小于就将开始索引重新赋值为中间索引加 1, 大于就将结束索引重新赋值为中间索引减 1.
此解法的时间复杂度是 O(log2(n)), 空间复杂度是 O(1).
- public int search(int[] nums, int target) {
- if (target <nums[0] || target> nums[nums.length-1]) {
- return -1;
- }
- int start = 0, end = nums.length-1;
- while (start <= end) {
- int mid = (end+start)/2;
- if (nums[mid] == target) {
- return mid;
- } else if (nums[mid]> target) {
- end = mid-1;
- } else {
- start = mid+1;
- }
- }
- return -1;
- }
03 第二种解法
直接使用循环依次匹配, 如果遍历完数组所有元素都没有匹配上, 就返回 - 1.
此解法的时间复杂度是 O(n), 空间复杂度是 O(1).
- public int search(int[] nums, int target) {
- if (target <nums[0] || target> nums[nums.length-1]) {
- return -1;
- }
- for (int i=0; i<nums.length; i++) {
- if (target == nums[i]) {
- return i;
- }
- }
- return -1;
- }
04 第三种解法
因为数组元素的取值范围定了, 我们可以使用新的数组, 以旧数组元素值为索引, 旧元素索引为值, 最后以目标值为索引, 在新数组中查找, 如果其值为 0, 就返回 - 1, 反之返回其值.
此解法的时间复杂度是 O(n), 空间复杂度是 O(n).
- public int search(int[] nums, int target) {
- if (target <nums[0] || target> nums[nums.length-1]) {
- return -1;
- }
- int[] temp = new int[20000];
- for (int i=0; i<nums.length; i++) {
- temp[nums[i]+10000] = i+1;
- }
- return temp[target+10000] == 0 ? -1 : temp[target+10000]-1;
- }
05 小结
算法专题目前已日更超过四个月, 算法题文章 165 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/01fa7d46ccba