Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

【LeetCode】Search Insert Position

___Moongazer 2019-09-12 11:04:00 阅读数:15 评论数:0 点赞数:0 收藏数:0

【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.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 4:

Input: [1,3,5,6], 0
Output: 0

【AC code】

一、暴力法  时间复杂度:O(n)

 class Solution {
     public int searchInsert(int[] nums, int target) {
         for (int i = 0; i < nums.length; i++) {
             if (nums[i] >= target) return i;
         }
         return nums.length;
     }
 }
View Code

 

二、二分查找法  时间复杂度:O(logn)

 class Solution {
     public int searchInsert(int[] nums, int target) {
         int arrlen = nums.length;
         if (nums[arrlen - 1] < target) return arrlen;
         int left = 0, right = arrlen - 1;
         while (left <= right) {
             int mid = left + (right - left) / 2;
             if (nums[mid] > target) right = mid - 1;
             else if (nums[mid] < target) left = mid + 1;
             else return mid;
         }
         return left;
     }
 }
View Code

 

版权声明
本文为[___Moongazer]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/moongazer/p/11510798.html