乘风破浪：LeetCode真题_035_Search Insert Position

乘风破浪：LeetCode真题_035_Search Insert Position

一、前言

    这次的问题比较简单，也没有限制时间复杂度，但是要注意一些细节上的问题。

二、Search Insert Position

2.1 问题

2.2 分析与解决

    同样也可以使用二分查找和直接查找。

public class Solution {
    /**
     * <pre>
     * 原题
     * [1,3,5,6], 5 → 2
     * [1,3,5,6], 2 → 1
     * [1,3,5,6], 7 → 4
     * [1,3,5,6], 0 → 0
     *
     * 题目大意
     * 给定一个排序数组，和一个指定的值，如果找到这个值，返回这个值位置，如果没有找到，返回这个值在数组中的插入位置。
     * 假设数组中没有重复的元素。
     *
     * 解题思路
     * 一、最直接的查找算法，从左向右搜索。
     * 二、使用二分查找算法。
     */
    public int searchInsert(int[] A, int target) {

        int mid;
        int lo = 0;
        int hi = A.length - 1;

        while (lo <= hi) {
            //注意这里的等于，就是为了查找不中返回lo方便
            mid = lo + (hi - lo) / 2;

            if (A[mid] == target) {
                return mid;
            } else if (A[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return lo;
    }

    public int searchInsert2(int[] A, int target) {

        if (A == null) {
            return -1;
        }

        int i;
        for (i = 0; i < A.length; i++) {
            if (A[i] >= target) {
                return i;
            }
        }

        return i;
    }
}

 

三、总结

    很多东西我们反复的练习就是为了能够打开自己的思维，从而推陈出新。