每日一道 LeetCode (10)：搜索插入位置

?

每天 3 分鐘，走上算法的逆襲之路。

?

前文合集

每日一道 LeetCode 前文合集

代碼倉(cāng)庫(kù)

GitHub：https://github.com/meteor1993/LeetCode

Gitee：https://gitee.com/inwsy/LeetCode

題目：搜索插入位置

題目來(lái)源：https://leetcode-cn.com/problems/search-insert-position/

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

你可以假設(shè)數(shù)組中無(wú)重復(fù)元素。

示例 1:

輸入:?[1,3,5,6],?5
輸出:?2

示例 2:

輸入:?[1,3,5,6],?2
輸出:?1

示例 3:

輸入:?[1,3,5,6],?7
輸出:?4

示例 4:

輸入:?[1,3,5,6],?0
輸出:?0

解題思路：暴力方案

經(jīng)?？次椅恼碌耐瑢W(xué)看到這這道題都應(yīng)該感覺(jué)是小意思了，最簡(jiǎn)單也是最好想的方案，直接迭代數(shù)字，用目標(biāo)字符進(jìn)行比較，如果大于等于當(dāng)前的字符，直接返回當(dāng)前的位置就好，如果一直都沒(méi)達(dá)成這個(gè)條件，說(shuō)目標(biāo)字符是最大的，循環(huán)結(jié)束返回。

感覺(jué)說(shuō)的太抽象了，直接上代碼比較簡(jiǎn)潔：

public?int?searchInsert(int[]?nums,?int?target)?{

????if?(nums[nums.length?-?1]?return?nums.length;

????for?(int?i?=?0;?i?????????if?(nums[i]?>=?target)?{
????????????return?i;
????????}
????}
????return?0;
}

解題思路：二分法

既然這道題的主要考察的是查找位置，怎么能少得了我赫赫有名的「二分法」。

尷尬的是我在做這道題的時(shí)候并沒(méi)有想到這個(gè)算法，看來(lái)還是刷題少，需要多加練習(xí)。

二分法的思路就不介紹了吧，這個(gè)思路不清楚可以單獨(dú)私信我。

直接上代碼：

public?int?searchInsert_1(int[]?nums,?int?target)?{
????int?n?=?nums.length;
????int?left?=?0,?right?=?n?-?1,?ans?=?n;
????while?(left?<=?right)?{
????????int?mid?=?((right?-?left)?>>?1)?+?left;
????????if?(target?<=?nums[mid])?{
????????????ans?=?mid;
????????????right?=?mid?-?1;
????????}?else?{
????????????left?=?mid?+?1;
????????}
????}
????return?ans;
}

上面這兩種方法雖然得到了相同的執(zhí)行用時(shí)，在大量數(shù)據(jù)的情況下應(yīng)該是二分法所使用的耗時(shí)更少，畢竟暴力方案在最差的情況下需要每次都把整個(gè)數(shù)組遍歷一遍，而相對(duì)而言二分法所需要的平均循環(huán)次數(shù)更少。