给出一个按排序顺序的整数列表，例如 [-9，-2，0，2，3] ，我们必须对每个元素求平方并返回结果排序。因此，输出为： [0，4，4，9，9，81] 。
Given a list of integers in sorted order, say, [-9, -2, 0, 2, 3], we have to square each element and return the result in a sorted order. So, the output would be: [0, 4, 4, 9, 81].
我可以找出两种方法：
O（NlogN）方法-我们将每个元素的平方插入哈希集中。然后将元素复制到列表中，对其进行排序然后返回。
O(NlogN) approach - We insert the square of each element in a hashset. Then copy the elements into a list, sort it and then return it.
O（n）方法-如果输入元素有界限（例如-100到-100），则我们创建一个大小为20000的布尔列表（存储-10000到10000）。对于每个输入元素，我们将相应的平方数标记为true。例如，对于输入中的 9 ，我将布尔数组中的 81 标记为true。然后遍历此布尔列表，并将所有真实元素插入返回列表。请注意，在此我们假设-输入元素有一个界限。
O(n) approach - If there is a bound for the input elements (say -100 to -100), then we create a boolean list of size 20000 (to store -10000 to 10000). For each of the input elements, we mark the corresponding square number as true. For e.g., for 9 in the input, I will mark 81 in the boolean array as true. Then traverse this boolean list and insert all the true elements into a return list. Note that in this we make an assumption - that there is a bound for the input elements.
是否存在某种方式其中我们可以在 O（n）时间内完成操作，甚至无需为输入假设任何限制？
Is there some way in which we could do it in O(n) time even without assuming any bounds for the input?
推荐答案我可以想到一种 O（n）方法
完成：）
更多推荐
O（n）中的列表中数字的平方平方？
发布评论