锐客网

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

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

IT技术unicode


「示例:」
「说明」:
思路
继续沿着上一道题的思路 。
移动零
代码如下：
时间复杂度：O(n) 。
题目：977. 有序数组的平方 ()
难度：简单
描述：
给你一个按「非递减顺序」排序的整数数组nums，返回「每个数字的平方」组成的新数组，要求也按「非递减顺序」排序 。
题目示例
思路
「暴力排序法」
这道题一看 ， 最直观的做法是什么呢？
先求数字平方的数组 ， 然后再把新数组排序 。
代码也好写：
时间复杂度：遍历时间复杂度O(n)，快排时间复杂度O(nlogn) ， 所以时间复杂度O(n+nlogn) 。
思路
「双指针法」
我们连写几道双指针了，这道题能不能用双指针实现呢？
我们分析一下，这个数组在取平方之前 ， 是有序的 ， 那么它绝对值最大的数一定是在两端的 。
所以我们可以定义两个指针，一个指向最左端 ， 一个指向最右端 ， 比较两者平方的大?。?大的平方放入结果数组，并移动指针 。
有序数组的平方
代码如下：
时间复杂度：O(n) 。
题目：1. 两数之和 ()
难度：简单
描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标 。
你可以假设每种输入只会对应一个答案 。但是，数组中同一个元素在答案里不能重复出现 。
你可以按任意顺序返回答案 。
题目示例
思路：
「暴力解法」
上来我们先来个最简单的暴力解法，大家应该都知道冒泡排序吧，类似的两层循环 。
两层循环
代码写起来也很简单：
时间复杂度：看到这个双循环 ， 就知道时间复杂度O(n2) 。
「哈希辅助法」
时间复杂度O(n2)多少有点过了 ， 这道题的重点是两个元素相加之和的判断 。
我们可以用一个Hash集合把元素存起来，这样一来遍历一遍就够了，例如目标和9，当前元素2，只需要判断集合里是否有元素7就行了 。
时间复杂度：从Hash查询和取值时间复杂度都是O(1) ， 所以整体时间复杂度是O(1) 。
题目：15. 三数之和 ()
难度：简单
描述：
给你一个包含 n 个整数的数组 nums ， 判断 nums 中是否存在三个元素 a ， b，c  ， 使得 a + b + c = 0 ？请你找出所有和为0且不重复的三元组 。
注意：答案中不可以包含重复的三元组 。
题目示例
思路：
「哈希法」
做完两数之和以后 ， 我们首先想到的就是哈希法 。
两层循环，取到a，b ， 再通过 0-(a+b) 来确定c 。
但是这里还有一个问题，答案中不可以包含重复的三元组 。
所以，我们还要想办法去掉Hash里的重复元素 。
可以加入一个约束 ， 第三个数的索引大于第二个数才存入 。
时间复杂度：双循环，O(n2) 。
虽然这么也写出来了，但是，说实话，很难写出没有问题的代码 。
我们写了这么多双指针，那么有没有可能用双指针的方式呢？
「双指针法」
首先对数组进行排序 ， 然后遍历数组 。
然后再在当前节点后面取左右指针 ， 判断左右指针的值是否等于0-nums[i]，然后分别左右移动 。
怎么去重呢？
满足条件时，看左指针的值是否和前一个位置相等，右指针的值是否和和它后一个位置的值相等 。
双指针法
代码如下：

推荐阅读


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

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