LeetCode 每日一题(day 1)

代码星冰乐

专注成就未来

首页 归档 关于

LeetCode 每日一题(day 1)

Feb 13, 2019 | haifeiWu | Java | 阅读
文章目录
  1. 1. 题目
  2. 2. 解决方案
    1. 2.1. 方法一:排序
    2. 2.2. 方法二:双指针

作 者:haifeiWu
原文链接:https://www.hchstudio.cn/article/2019/6bf7/
版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。


由于版权原因,请阅读原文 --> LeetCode 每日一题(day 1)

关注我们

作 者:haifeiWu
原文链接:https://www.hchstudio.cn/article/2019/6bf7/
版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。

作 者:haifeiWu
原文链接:https://www.hchstudio.cn/article/2019/6bf7/
版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。

题目

题目描述:

给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。

示例 1:

1
2
输入:[-4,-1,0,3,10]
输出:[0,1,9,16,100]

示例 2:

1
2
输入:[-7,-3,2,3,11]
输出:[4,9,9,49,121]

提示:

  1. 1<= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A 已按非递减顺序排序。

解决方案

方法一:排序

思路与算法

创建一个新的数组,它每个元素是给定数组对应位置元素的平方,然后排序这个数组。

1
2
3
4
5
6
7
8
9
public int[] sortedSquares(int[] A) {
int[] B = new int[A.length];

for (int i=0; i < A.length; i++) {
B[i] = (A[i]) * (A[i]);
}
Arrays.sort(B);
return B;
}

复杂度分析

  • 时间复杂度:O(N \log N)O(NlogN),其中 NN 是数组 A 的长度。

  • 空间复杂度:O(N)O(N)。

方法二:双指针

思路

因为数组 A 已经排好序了, 所以可以说数组中的负数已经按照平方值降序排好了,数组中的非负数已经按照平方值升序排好了。

举一个例子,若给定数组为 [-3, -2, -1, 4, 5, 6],数组中负数部分 [-3, -2, -1] 的平方为 [9, 4, 1],数组中非负部分 [4, 5, 6] 的平方为 [16, 25, 36]。我们的策略就是从前向后遍历数组中的非负数部分,并且反向遍历数组中的负数部分。

算法

我们可以使用两个指针分别读取数组的非负部分与负数部分 —— 指针 i 反向读取负数部分,指针 j 正向读取非负数部分。

那么,现在我们就在使用两个指针分别读取两个递增的数组了(按元素的平方排序)。接下来,我们可以使用双指针的技巧合并这两个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int[] sortedSquares(int[] A) {
int N = A.length;
int j = 0;
while (j < N && A[j] < 0)
j++;
int i = j-1;

int[] ans = new int[N];
int t = 0;

while (i >= 0 && j < N) {
if (A[i] * A[i] < A[j] * A[j]) {
ans[t++] = A[i] * A[i];
i--;
} else {
ans[t++] = A[j] * A[j];
j++;
}
}

while (i >= 0) {
ans[t++] = A[i] * A[i];
i--;
}
while (j < N) {
ans[t++] = A[j] * A[j];
j++;
}

return ans;
}

关注我们

作 者:haifeiWu
原文链接:https://www.hchstudio.cn/article/2019/6bf7/
版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。

分享
算法
Integer 中你所不知道的ArrayBlockingQueue 阻塞队列
微信关注我们
分类
  • Android8
  • Go1
  • Java57
  • Kotlin2
  • Python2
  • Redis1
  • 工具1
  • 总结7
  • 旅游日记1
标签
算法 ChanghuiN Android haifeiWu Java 译文 Docker Spring Boot 源码解析 设计模式 工具 web hexo 学习笔记 Kotlin 总结 MySQL netty Redis Python WebFlux 性能测试 golang 配置中心 Nginx 性能优化 旅游日记 Shell 散列表 源码 问题排查
最近文章
  • Kafka Consumer 的 Rebalance 机制
  • 实时数据并发写入 Redis 优化
  • Redis 与 Lua 使用中的小问题
  • Git 命令
  • 二分查找算法细节详解
  • 实现自己的 RPC 框架(二)
  • lang3 的 split 方法误用
  • [译] 为什么String在Java中是不可变的
  • 双重检查锁定与单例
  • LRU 算法
福利专区
    免费SSL证书
      阿里云红包
        腾讯云专属福利
        Copyright © 2019 代码星冰乐. Powered by ChanghuiN. 版权所有 晋ICP备15001365号
        特别感谢: 云服务器服务商 、 CDN 服务商