社区首页 >专栏 >LeetCode49|搜索旋转排序数组

LeetCode49|搜索旋转排序数组

码农王同学

发布于 2020-09-10 07:42:10

29100

代码可运行

文章被收录于专栏：后端Coder后端Coder

运行总次数：0

代码可运行

1,问题简述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

2，示例

示例 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，题解思路

键值对集合的使用

4，题解程序

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.stream.IntStream;

public class SearchTest {
    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        int search = search3(nums, target);
        long startTime = System.currentTimeMillis();
        System.out.println("search = " + search);
        long endTime = System.currentTimeMillis();
        long totalTime = endTime - startTime;
        System.out.println("totalTime = " + totalTime + "毫秒");
    }

    public static int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int length = nums.length;
        HashMap<Integer, Integer> hashMap = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            hashMap.put(i, nums[i]);
        }
        Optional<Map.Entry<Integer, Integer>> entry = hashMap.entrySet().stream().filter(x -> x.getValue() == target).findFirst();
        if (entry.isPresent()) {
            return entry.get().getKey();
        }
        return -1;
    }

    public static int search2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int length = nums.length;
        int[] newNums = new int[length];
        System.arraycopy(nums, 0, newNums, 0, length);
        int newLength = newNums.length;
        return IntStream.range(0, newLength).filter(i -> newNums[i] == target).findFirst().orElse(-1);
    }

    public static int search3(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[start] <= nums[mid]) {
                if (target >= nums[start] && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}

5，题解程序图片版

6，总结

键值对集合的使用，凑字数来了，曾经我会后悔自己有些事情没有去做，但是随着自己对自己的一通分析，觉得自己本身还是有一些优点的，后悔有用吗？就这样一步步问自己，经过读书的理解，自己慢慢明白了一个道理，人生走的每一步都算数。很久之前的文章就给与了自己这句话，急功近利，欲速则不达，找好自己的人生路，慢慢跑吧，这样自己的人生方向才有了自己独有的特点。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-09-05，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法