C ++将值移动到数组的开头

问题描述 投票:0回答:1

需要在数组的开头移动所有小于1的值(没有SORT,并且需要没有第二个数组的解决方案)

例如:

START ARRAY: {-2.12, -3, 7.36, 6.83, -1.82, 7.01}

FINISH ARRAY: {-2.12, -3, -1.82, 7.36, 6.83, 7.01}

有我的解决方案,但效果不佳,因为最终我们收到了:

FINISH ARRAY: {-2.12, -3, -1.82, 6.83, 7.36, 7.01}

小于1的值移动到数组的开头,但4和5个元素的顺序不正确

#include <iostream>

using namespace std;

int main() {
    double arr[6] = {-2.12, -3, 7.36, 6.83, -1.82, 7.01};

    cout << "Start array: " << endl;
    for (int x = 0; x < 6; x++) {
        cout << arr[x] << ", ";
    }

    int index=0;
    double temp;
    for (int i = 0; i < 6; i++) { 
        if (arr[i] < 1) {
            temp=arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
            index++;
        }
     }
    cout << endl << "FINISH ARRAY: " << endl;
    for (int x = 0; x < 6; x++) {
        cout << arr[x] << ", ";
    }



    return 0;
}
c++ arrays
1个回答
1
投票

使用std::stable_partition

std::stable_partition

[如果您想自己实现它,请注意,就地稳定分区不能比std::stable_partition(std::begin(arr), std::end(arr), [](double d) { return d < 1; }); 时更好。任何运行时间为O(N log N)的算法均不正确。

基本思想是使用分而治之(类似于快速排序):

O(N)

[// Returns iterator to the first element of the second group template<class It, class Pred> It stable_partition(It first, It last, Pred pred) { if (first == last) return last; if (last - first == 1) return pred(*first) ? last : first; // Split in two halves auto mid = first + (last - first) / 2; // Partition the left half: [TTTTTFFFFF] // ^ left auto left = stable_partition(first, mid, pred); // Partition the right half: [TTTTTFFFFF] // ^ right auto right = stable_partition(mid, last, pred); // Rotate the centeral part: [TTTTTFFFFF] [TTTTTFFFFF] // [^ ^) return std::rotate(left, mid, right); } 本身很容易通过三个反转实现。

© www.soinside.com 2019 - 2024. All rights reserved.