LeetCode & Q35-Search Insert Position-Easy-javaTutorial-php.cn

LeetCode & Q35-Search Insert Position-Easy

PHP中文网

Lepaskan： 2017-07-11 18:12:27

asal

1351 orang telah melayarinya

Array Binary Search

Description:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

my Solution:

<code class="sourceCode java"><span class="kw">public</span> <span class="kw">class</span> Solution {
    <span class="kw">public</span> <span class="dt">int</span> <span class="fu">searchInsert</span>(<span class="dt">int</span>[] nums, <span class="dt">int</span> target) {
        <span class="dt">int</span> i = <span class="dv">0</span>;
        <span class="kw">for</span>(i = <span class="dv">0</span>; i < nums.<span class="fu">length</span>; i++) {
            <span class="kw">if</span>(target <= nums[i])
                <span class="kw">break</span>;
        }
        <span class="kw">if</span>(i < nums.<span class="fu">length</span>)
            <span class="kw">return</span> i;
        <span class="kw">else</span>
            <span class="kw">return</span> i++;
    }
}</code>Salin selepas log masuk

Best Solution:

<code class="sourceCode java"><span class="kw">public</span> <span class="dt">int</span> <span class="fu">searchInsert</span>(<span class="dt">int</span>[] A, <span class="dt">int</span> target) {
    <span class="dt">int</span> low = <span class="dv">0</span>, high = A.<span class="fu">length</span><span class="dv">-1</span>;
    <span class="kw">while</span>(low<=high){
        <span class="dt">int</span> mid = (low+high)/<span class="dv">2</span>;
        <span class="kw">if</span>(A[mid] == target) <span class="kw">return</span> mid;
        <span class="kw">else</span> <span class="kw">if</span>(A[mid] > target) high = mid<span class="dv">-1</span>;
        <span class="kw">else</span> low = mid<span class="dv">+1</span>;
    }
    <span class="kw">return</span> low;
}</code>Salin selepas log masuk

差别就在于，我用的是从首到尾循环，没有完全利用好已排序这个条件。最优解用的是二分法，基本是排序里的算法。

Atas ialah kandungan terperinci LeetCode & Q35-Search Insert Position-Easy. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

LeetCode &amp; Q35-Search Insert Position-Easy

LeetCode & Q35-Search Insert Position-Easy