有效地对排序后的数组中的每个元素进行平方运算，使其保持排序状态

void bubbleSort(int *arr, int length);

int main(int argc, const char * argv[]) {

    int arr[] = {-3,-2,0,4,5,8};

    for(int i = 0; i < 6; i++) {
        arr[i] *= arr[i];
    }

    bubbleSort(arr, 6);

    for(int j = 0; j < 6; j++)
        cout << arr[j] << endl;
}

void bubbleSort(int *arr, int length) {
    int temp;

    for(int i = 0; i < length; i++) {
        for(int j = 0; j < length; j++) {
            if(arr[j] < arr[j+1]) {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

#1 楼

可以在O（n）时间内完成。将数组分为两个逻辑部分。正面及负面。然后将平方应用于两个数组中的每个元素。然后合并数组（可以在O（n）中完成合并），但是以相反的顺序将数组与以前的负整数合并，因为其值将被反转。

#2 楼

如果对数组进行排序。
那么唯一会发生的重新排序是将负数转换为正数（因为负数的平方会导致正数）。所以负数将需要重新排序为正数。

  [ -10, -6, -4, -2, 1, 3, 5, 8]
                   ^
                   Split

您实际上可以只考虑这两个单独的排序数组（一个按负方向排序）但这仅意味着使用-而不是++对其进行迭代（我们有一个迭代器）。那）。完成后，对值执行平方运算。该算法为O（n）。尽管您要遍历该数组两次。

唯一的优化是在执行合并的同时执行平方（快速自定义迭代器可以解决此问题）。解决方案是O（n），但它将是数组的单个遍历（并不困难）。

void mergeSortedArray(std::vector<int>& data)
{

    // Find the iterator range for the positive values.
    using iter          = std::vector<int>::const_iterator;
    iter  endPositive   = std::end(data);
    iter  loopPositive  = std::find_if(std::begin(data), std::end(data),
                                       [](int val) {return val >=0;});

    // Find the iterator range for the negative values.
    using reve          = std::reverse_iterator<iter>;
    reve  endNegative   = reve(std::begin(data));
    reve  loopNegative  = reve(loopPositive);

    // Create an array to put the results into.
    std::vector<int>  result;
    result.reserve(data.size());

    // Perform a standard merge
    std::merge(loopPositive, endPositive, loopNegative, endNegative,
               SquarePushBackIterator(result),
               [](int val1, int val2){return std::abs(val1) < std::abs(val2);});

    // Use move assignment to put the result in the output vector.
    // Alternatively we could return an array by value.
    data = std::move(result);
}

只需要一个本地客户迭代器。
这将对值进行平方并根据分配将其推入容器。

class SquarePushBackIterator
    : public std::iterator<std::output_iterator_tag,int>
{
    std::vector<int>& dst;
    public:
        SquarePushBackIterator(std::vector<int>& dst) : dst(dst) {}
        // These just return references to the iterator.
        // The only operation that matters is assignment.
        SquarePushBackIterator& operator*()     {return *this;}
        SquarePushBackIterator& operator++()    {return *this;}
        SquarePushBackIterator& operator++(int) {return *this;}

        // The assignment squares and inserts into the destination.
        void operator=(int val)
        {
            dst.push_back(val * val);
        }
};

#3 楼

由于已排序，因此您可以遍历数组一次，比较数组中第一项和最后一项的绝对值，然后基于较大的那个，对该项进行平方，然后将值放入新数组的最后一项中。通过增加前索引或减小后索引（取决于哪个值较大）来重复此过程，然后将下一个最大的项目放到新数组的倒数第二个项目中，依此类推。

基本上，您在一个循环中同时对值进行排序和平方。

int arr[] = {-3,-2,0,4,5,8};
int size = 6;
int newArr[size];

int newArrInd = size - 1;
int front = 0;
int back = size - 1;

for(int i = 0; i < size; i++) {
    if (abs(arr[front]) > abs(arr[back])){
        newArr[newArrInd--] = arr[front] * arr[front];
        front++;
    }
    else{
        newArr[newArrInd--] =  arr[back] * arr[back];
        back--;
    }
}

for(int j = 0; j < size; j++)
    cout << newArr[j] << endl;

#4 楼

这是一个可能更简单的解决方案（运行时间可能会稍长；尽管仍然是\ $ O（n）\ $）。当然，基本思想是只需要反转负数（在平方之前或之后，实际上并不重要）。它不具有基础容器将在整个过程中保持排序的属性；是否真正需要（或者是否仅是必须遵守该准则的最终结果）尚不是100％明确。

#include <algorithm>
#include <iterator>

template <typename Iterator>
void square_and_sort(Iterator begin, Iterator end)
{
    using value_type = typename std::iterator_traits<Iterator>::value_type;

    auto first_positive = std::find_if(begin, end, 
            [](const value_type& v) { return v >= value_type{}; });
    std::reverse(begin, first_positive);
    std::transform(begin, end, begin,
            [](const value_type& v) { return v * v; });
    std::inplace_merge(begin, first_positive, end);
}

有效地： br />

查找第一个零或正值，
反转所有值直至该第一个零或正值（因为它们必须为负），最后
将平方的负值和平方的正值合并回原位。

#5 楼

您的解决方案

如果我想对数组进行平方和排序的显而易见的解决方案，它将看起来像这样：
不使用标准库的要求？它使您免于实现无聊，困难和容易出错的事情（例如排序算法）的痛苦。负数变为正数，使数组不再排序。我的想法是找到第一个非负数的索引mid，然后对整个数组求平方。部分列表[begin, mid[以相反的顺序排序，并且部分列表]mid, end[已经正确排序。可以将两个排序列表有效地排序为一个排序列表。可以使用std::merge来补偿第一个列表的反向顺序。

#include <algorithm>
#include <iostream>

int main(){
    //arguably arr should be an std::array or even auto for an std::initializer_list
    int arr[] = { -3, -2, 0, 4, 5, 8 };
    //square array
    std::transform(std::begin(arr), std::end(arr), std::begin(arr),
        [](int n){ return n * n; }
    );
    //sort array
    std::sort(std::begin(arr), std::end(arr));
    //print result
    for (const auto &i : arr)
        std::cout << i << ' ';
}

此实现将第二个数组用于合并列表。可能可以就地进行，但这需要更多的努力。我的解决方案将复杂度从O（n * log（n））降低到O（n），但是将空间复杂度从O（1）更改为O（n），这并不是严格必要的。我可能会偏爱您的解决方案，因为它很容易，除非经过性能分析证明效率低下是一个重大问题。

#6 楼

如果允许在平方后对数组进行未排序，然后对其进行排序，请至少使用std::sort；或者，为了获得更好的时间性能但更多地占用空间，请使用std::merge。如果标准库超出了采访的范围，请运行。 :)

另一方面，如果必须在更改每个元素后进行排序，请利用标准库的其他部分，例如std::lower_bound和std::rotate。请注意执行操作的顺序，以免冒平方两次的风险。

#7 楼

我相信您错过了一项关键要求，即需要保持阵列排序。您的解决方案没有。输入中的负值开始排序，但是当您平方它们时，它们会反转。然后，您可以使用冒泡排序对它进行纠正。

有一种方法可以使所有数据始终保持排序。这不是\ $ O（n）\ $操作。

使用的算法是对数组右侧所有大于abs值的值进行平方运算。最左边的值。

一旦找到较小的值，您就会知道需要在该点插入最左边的值平方。向左移动所有值，插入正方形，然后继续。

您的代码非常类似于C，并且类似C的实现为：

>
基于矢量的基本解决方案将是：使用的算法。请注意，在某些情况下，值是重复的（在移位过程中），但是数组在任何时候都不会乱序。

#8 楼

如果对数组进行了排序，则可以使用二进制搜索实现找到从负到正的位置。

{-3 -2 | 0 4 5 8}
     A   B

然后使用该位置，比较左边的数字在右边。取绝对值较小的那个数字，将其平方添加到新数组的下一个位置，然后将其指针从中间移开，直到A达到-1或B达到长度

算法的迭代方法

array    {-3 -2 | 0 4 5 8}
pointer       A   B
squares  {              }


abs(arr[B]) < ab(arr[A])
B++
array    {-3 -2 | 0 4 5 8}
pointer       A     B
squares  {0              }

abs(arr[B]) > ab(arr[A])
A--
array    {-3 -2 | 0 4 5 8}
pointer    A        B
squares  {0 4            }

abs(arr[B]) > ab(arr[A])
A--
array    {-3 -2 | 0 4 5 8}
pointer  A          B
squares  {0 4 9          }

A == -1 && B != length
B++
array    {-3 -2 | 0 4 5 8}
pointer  A            B
squares  {0 4 9 16        }

etc...

我希望自己能很好地解释一下，它基本上是合并排序。据我所知，这需要O（log（n）（已删除：*）+ n）时间和O（n）空间。

#9 楼

这取决于排序算法的实现。由于数组已经大部分排序或以降序排序等情况，因此对于随机数而言，好的实用排序算法不会得到优化，而是针对实际情况进行优化。如果只对所有数字求平方，然后调用实现提供的排序算法，则很可能会发现您的数组由大量的降序整数组成，然后由大量的升序组成排序，并以最佳方式合并两个序列。

#10 楼

最快的方法是使用两个索引：

int main()
{
    vector<double> k={-5, -3, 1, 2 ,6 };
    deque<double> l;
    int p1=0,p2=k.size()-1;

    double s ,e;
    do {
        s=k[p1]; e=k[p2];
        if(s*s>e*e) { l.push_front(s*s); p1++; }
        else { l.push_front(e*e); p2--; }
    } while(p2>=p1);
}

只插入一次
每个开关仅测试两次
读取值\ $ 2 * n \ $
由于完美的别名向量，最坏的情况\ $ 2 * n \ $测试

只需添加int main()并更改测试以使其适用于多个值（我认为这很明显）。

deque是你的朋友。

#11 楼

您可以考虑使用std::set通过插入成员函数对数组进行排序。

它是一个O（N * log（size（）+ N）），其中N是要插入的元素数。

根据http：// en .cppreference.com / w / cpp / container / set / insert

#include <iostream>
#include <set>
int main()
{
    using namespace std;
    int arr[] = { -3, -2, 0, 4, 5, 8 };

    set<int> sort_squae;

    // it will sort and square the array for free
    for (auto&& i : arr)
        sort_squae.insert(i * i);

    // print it
    for (const auto& i : sort_squae)
        cout << i << ' ';
}

#12 楼

直接问题


有没有办法更有效地执行此操作，也许是O（N）解决方案？


是的，可以比bubbleSort的O（n ^ 2）更有效。而且不行。一般比较排序算法的极限是O（n log n）。

面试问题


数组的排序算法被烘焙到大多数编程语言中，或者可以在库中找到[带有书籍的种类，如果不是语言标准的]。当然，它们不能直接处理任意对象，但是它们都可以适当地处理整数以达到通常将语言放入的目的。这些是现成的零件。 Knuth中有整整一章供任何需要认真对待的人使用。

在更改数组值的同时保持数组排序意味着并发语义。对于明智的面试官而言，这是一个棘手的问题。即使在O（n log n）中给出可靠的答案是可取的，但在O（n log n）中给出不可靠的答案通常比在O（n ^ 2）中给出可靠的答案要差。 /> C ++是面向对象的。这建议通过类和对象的语义进行封装。
C ++是C的一种形式。指针的操作是惯用法。它完全基于操纵指向记录的指针，而不是移动实际记录。有更糟糕的权威机构试图模仿。

解决这一问题的方案的骨架可能看起来像：
虽然这是一个玩具问题。购买Xtreme CPU，将所有内容存储在RAM中-甚至更好的L1缓存，然后开始飙车。但是最终的性能是调整而不是解决问题。复杂性保持不变。