代码之家 › 专栏 › 技术社区 › J. Doe

按O(n)排序的列表中的数字平方?

time-complexity algorithm

J. Doe · 技术社区 · 8 年前

给定一个按排序顺序排列的整数列表, [-9, -2, 0, 2, 3] ,我们必须对每个元素进行平方运算,并按排序顺序返回结果。因此,输出为: [0, 4, 4, 9, 81] 。

我可以想出两种方法:

O(NlogN) 方法-我们在哈希集中插入每个元素的平方。然后将元素复制到列表中,对其排序,然后返回。
O(n) 方法-如果输入元素有一个边界(比如-100到-100),那么我们创建一个大小为20000的布尔列表(存储-10000到10000)。对于每个输入元素,我们将相应的平方数标记为true。例如,用于 9 在输入中,我将标记 81 在布尔数组中为true。然后遍历这个布尔列表并将所有true元素插入到返回列表中。注意,在这里我们假设输入元素有一个界。

我们有什么办法可以做到这一点吗 O(n) 时间 即使没有为输入设置任何边界 ?

6 回复 | 直到 8 年前

Srini 8 年前

我能想到一个 O(n) 方法

将输入拆分为两个列表。一个是负数,我们把这个叫做列表 A 。一个是正数,一个是0,列表 B 。这是在保持输入顺序的同时完成的,这很简单: O(n)
反向列表 A. 。我们这样做是因为一旦平方,如果翻转,元素之间的关系就大于
将两个列表中的每一项放在适当的位置: O(n)
运行a merge 操作与合并排序的操作相似: O(n)
总计: O(n)

完成:)

Steve 8 年前

是否有某种方法可以在O(n)时间内完成,即使不假设输入有任何界限?

绝对地

由于原始列表已经排序,您很幸运!

给定两个数字x和y

如果 |x| > |y| 然后 x^2 > y^2

所以你所要做的就是把列表分成两部分,一部分是所有的负数,另一部分是所有的正数

将消极的一面颠倒过来,使之成为积极的一面

然后使用插入将这两个列表合并为一个列表。这是在 O(n) 因为两个列表都已排序。

从那里你可以计算出平方,然后把它们放入新的列表中。

Lavina Khushlani 6 年前

我们可以通过双指针技术来实现它。1个指针位于起点,另一个指针位于终点。比较正方形并相应地移动指针,然后在新列表的末尾开始分配max元素。时间=O(n) 空间=O(n)

你能就地做吗?减少空间复杂性。

Pritam Banerjee Ashish Karnavat 6 年前

这可以用O(n)时间和空间来完成。我们需要两个指针。以下是Java代码:

public int[] sortedSquares(int[] A) {
    int i = 0; 
    int j = A.length - 1;

    int[] result = new int[A.length];

    int count = A.length - 1;
    while(count >= 0) {
        if(Math.abs(A[i]) > Math.abs(A[j])) {
            result[count] = A[i]*A[i];
            i++;
        }
        else {
            result[count] = A[j]*A[j];
            j--;
        }
        count--;
    }

    return result;
}

从末尾开始比较绝对值。然后创建答案。

Ekta Sahu 4 年前

  class Solution {
        public int[] sortedSquares(int[] nums) {
            int left = 0;
            int right = nums.length -1;
            int index = nums.length- 1;
            int result[] = new int [nums.length];
            while(left<=right)
            {
                if(Math.abs(nums[left])>Math.abs(nums[right]))
                {
                    result[index] = nums[left] * nums[left];
                    left++;
                }
                else
                {
                    result[index] = nums[right] * nums[right];
                    right--;
                }
                index--;
            }
            return result;
        }
    }

通过使用朴素的方法,这个问题将非常简单,但需要O(nlogn)复杂性

为了解决O(n)中的这个问题,双指针方法是最好的方法。

创建与给定数组长度相同的新结果数组,并将其指针存储为数组长度
在数组的开头指定一个指针,然后在数组的最后指定另一个指针,因为我们知道任意一侧的最后一个元素都是最高的
```
 [-9, -2, 0, 2, 3]
```
比较-9和3绝对值
如果是左值,则将该值存储到结果数组中,并减小其索引值并增大左值,否则减小右值。

Akash Rathor 4 年前

Python3溶液。时间复杂度-O(N)和空间复杂度O(1)。

def sorted_squArrres(Arr:list) ->list:
    i = 0
    j = len(Arr)-1

    while i<len(Arr):
        if Arr[i]*Arr[i]<Arr[j]*Arr[j]:
            Arr.insert(0,Arr[j]*Arr[j])
            Arr.pop(j+1)
            i+=1
            continue

        if Arr[i]*Arr[i]>Arr[j]*Arr[j]:
            Arr.insert(0,Arr[i]*Arr[i])
            Arr.pop(i+1)
            i+=1
            continue
        else:
            if i!=j:
                Arr.insert(0,Arr[j]*Arr[j])
                Arr.insert(0,Arr[j+1]*Arr[j+1])
                Arr.pop(j+2)
                Arr.pop(i+2)
                i+=2
            else:
                Arr.insert(0,Arr[j]*Arr[j])
                Arr.pop(j+1)
                i+=1

            
 
    return Arr
        
    
X = [[-4,-3,-2,0,3,5,6],[1,2,3,4,5],[-5,-4,-3,-2,-1],[-9,-2,0,2,3]]
for i in X:
    # looping differnt kinds of inputs
    print(sorted_squArrres(i))

# outputs 
'''
[0, 4, 9, 9, 16, 25, 36]
[1, 4, 9, 16, 25]
[1, 4, 9, 16, 25]
[0, 4, 4, 9, 81]
'''