首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hakunamatata11
V2EX  ›  推广

[leetcode/lintcode 题解]字节跳动面试题:有序数组的平方

  •  
  •   hakunamatata11 · 40 天前 · 566 次点击
    这是一个创建于 40 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    在线评测地址: https://www.lintcode.com/problem/squares-of-a-sorted-array/?utm_source=sc-v2ex-fks0603

    样例 示例 1

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

    示例 2

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

    [题解] 先循环遍历数组 A,得到该数组每个位置数所对应的平方数,然后排序即可

    public class Solution {
        /**
         * @param A: The array A.
         * @return: The array of the squares.
         */
        public int[] SquareArray(int[] A) {
            for(int i = 0; i < A.length ; i++){
                A[i] = A[i] * A[i];
            } 
            Arrays.sort(A);
            return A;
        }
    }
    

    更多语言代码参见 https://www.jiuzhang.com/solution/squares-of-a-sorted-array/?utm_source=sc-v2ex-fks0603

    10 条回复    2020-06-07 09:09:11 +08:00
    wellsc
        1
    wellsc   40 天前 via iPhone
    这……
    iamben
        2
    iamben   40 天前 via iPhone
    这…直接用 sort()的话题目的意义是啥
    mxalbert1996
        3
    mxalbert1996   40 天前 via Android
    你管这叫算法。。。
    liuminghao233
        4
    liuminghao233   40 天前 via iPhone
    easy 难度不要要求太多...
    softtwilight
        5
    softtwilight   40 天前
    用首位两个指针,将平方更大的数放到数组尾部
    xingheng
        6
    xingheng   40 天前
    直接双端指针往中间遍历并且比较平方值就行了,不需要 sort,时间复杂度 O1,空间复杂度 On 。
    rrfeng
        7
    rrfeng   40 天前 via Android
    我先取中间看正负,然后挑正负数多的那一边开始算,算到符号变化之后开始插入排序

    或者正负都算出来然后归并

    还有啥降低复杂度的办法呢
    rrfeng
        8
    rrfeng   40 天前 via Android
    哦对双指针最优……
    luckyrayyy
        9
    luckyrayyy   40 天前
    @xingheng 双指针时间不是 On 么?
    xingheng
        10
    xingheng   37 天前
    @luckyrayyy 你说得对,是我想差了。逃...
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4161 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 07:41 · PVG 15:41 · LAX 00:41 · JFK 03:41
    ♥ Do have faith in what you're doing.