锐客网

  1. 首页 > 睿知 > it技术 > >

螺旋矩阵java代码 螺旋矩阵java实现( 四 )

IT技术unicode


请必须使用时间复杂度为 O(log n) 的算法 。
题目示例
思路：
二分查找比较简单 ， 但写对还要费点功夫，再做一道基本一样的题巩固一下 。
这道题基本一样，插入的位置可能有四种情况：
二叉树插入位置
代码如下：
时间复杂度：O(logn)
题目：34. 在排序数组中查找元素的第一个和最后一个位置 ()
难度：中等
描述：
给定一个按照升序排列的整数数组 nums，和一个目标值 target 。找出给定目标值在数组中的开始位置和结束位置 。
如果数组中不存在目标值 target，返回 [-1, -1] 。
进阶：
题目示例
思路：
看到时间复杂度O(log n)，数组有序 ， 我们知道，二分查找该上场了 。
但是这道题有点不一样，它需要寻找边界 。
那我们怎么办呢？
这就引入了寻找边界的二分查找 。
这道题的思路是什么呢？
我们分别用二分查找来寻找左边界和右边界 。
一般的二分查找：
注意，我们这里的返回条件是nums[mid] == target ，但是寻找边界的时候就不能这样了，因为我们不能确定mid是不是我们的边界 。
以寻找左边界为例，条件是target = nums[mid] 的时候，我们接着往左移动 。
寻找右边界也类似 。
代码如下：
时间复杂度：O(logn)
题目：27. 移除元素 ()
难度：简单
描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度 。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组 。
元素的顺序可以改变 。你不需要考虑数组中超出新长度后面的元素 。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的 ， 这意味着在函数里修改输入数组对于调用者是可见的 。
你可以想象内部操作如下:
思路
「暴力解法」
暴力解法没什么好说的，和上道题类似，找到要删除的元素，把它后面的元素全部向前移动一位 。
暴力解法
这里有两点需要注意：
代码如下：
时间复杂度：O(n2) 。
「双指针法」
双指针法，是数组和链表题中非常常用的一种方法 。
这道题用双指针法怎么解决呢？
定义两个指针，一个前，一个后 。没有找到目标的时候front和after一起移动，找到目标的时候 ， after停下来 ， front接着移动，把front指向的值赋给after指向的值 。
这样一来，双指针就通过一个循环完成了双循环完成的事情 。
双指针法
代码如下：
时间复杂度：O(n) 。
题目：27. 移除元素 ()
难度：简单
描述：
给你一个有序数组 nums  ， 请你 原地 删除重复出现的元素，使每个元素 只出现一次，返回删除后数组的新长度 。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成 。
说明:
为什么返回数值是整数 ， 但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的 。
你可以想象内部操作如下:
题目示例
思路
趁着上一道题劲儿还没缓过来 ， 赶紧做一道基本一样的巩固一下 。
直接上代码：
时间复杂度：O(n) 。
题目：283. 移动零 ()
难度：简单
描述：
给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序 。

推荐阅读


上一篇：gislog表示的简单介绍

下一篇：玩具直播间投放技巧，玩具直播间装修图