当前位置:网站首页>Search for insertion position

Search for insertion position

2020-12-06 09:02:12 osc_ tmxtbi57

Search insert location (easy)

A better reading experience should be :

  1. Examine the subject - reflection
  2. Answer the questions
  3. Arrangement - inductive

One 、 subject

LeetCode Topic link :35. Search for the insertion location

Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence .

You can assume that there are no duplicate elements in the array .

Example 1:

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

Example 2:

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

Two 、 Answer key

Analyze the problem stem

It's important to analyze the topic , Every time I read the topic, I should thank you for reading comprehension , In this question , We learned that :

  1. An array is an ordered array
  2. No repeating elements

Answer 1 ( Violence law )

When it comes to the law of violence , It's the frequent use of traversal , And there's no such thing as “ tricks ”, From top to bottom, it's all real !

Time complexity :O(n)
Spatial complexity :O(1)

Ideas

  • Find the first match target Big elements , Its subscript , It's the answer .

Realization

var searchInsert = function(nums, target) {
   
   
  const len = nums.length;
  for (let i = 0; i < len; i++) {
   
   
    if (nums[i] >= target) {
   
   
      return i;
    }
  }
  return len;
};

Explanation 2 ( Dichotomy )

Find in a sorted array , We can use Dichotomy

Here's what we're trying to do : Find a subscript index, We were looking for it nums[index] <= target First value of .

If you can't find it , The length of the array is returned

Time complexity :O(log(n))
Spatial complexity :O(1)

var searchInsert = function(nums, target) {
   
   
  const len = nums.length;
  let left = 0; // Left boundary 
  let right = len - 1; //  Right border 
  let ans = len; //  Return value , Note that if the target is not in the array , Returns the length of the array 
  while (left <= right) {
   
   
    mid = ((right - left) >> 1) + left;
    if (target <= nums[mid]) {
   
   
      //  Prove that the left boundary is inside the array 
      ans = mid; //  Update return value 
      right = mid - 1;
    } else {
   
   
      left = mid + 1;
    }
  }
  return ans;
};

3、 ... and 、 At the end

This is the first article on dichotomy , What does dichotomy do , And other scenarios I'll send out in a new chapter , Mutual encouragement

About me

  • flower : Afterglow
  • WX:j565017805
  • addiction JS, Level co., LTD. , Learning with an open mind

Other precipitates

If you finally see , Let's have a three company company , This is the biggest encouragement for me !

版权声明
本文为[osc_ tmxtbi57]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201206085959973s.html