给定一个数组 'a' 和一个整数 'x'，排列 (就地) 的元素使得所有元素 <x come before all the elements >='x'

Question

此外，保留两个组中元素的原始相对顺序（即小于 'x' 的元素组成一组，等于或大于 'x' 的元素组成另一组。相对顺序应该在两个组中都保留。）

例1：-

a={2,6,3,5,1,7}

x=5

Output : 2 3 1 6 5 7

All the elements smaller than 5 come before 5 and the relative order of the moved elements is 
   preserved (2,3,1) & (6,5,7)

例2：-

a={1,4,2,5,3}

x=4

output : 1 2 3 4 5

最初的问题是针对单向链表的。我为一个数组编写了算法，我想知道它是否可以移植到链表变体中。另外，有更好的方法吗？

   #include <bits/stdc++.h>
using namespace std;

void swap(vector<int> &a, int i, int j)
{
    int i2 = i;
    int x = a[j];
    int temp1 = a[i];
    int temp2;
    while (i < j)
    {
        temp2 = a[i + 1];
        a[i + 1] = temp1;
        temp1 = temp2;
        i++;
    }
    a[i2] = x;
}

void solve(vector<int> &a, int num)
{
    int n = a.size();
    int i = 0, j = 1;
    while (j < n)
    {
        if (a[i] < num)
            i++;
        if (a[i] >= num && a[j] < num)
            swap(a, i, j);
        j++;
    }
}

int main()
{
    vector<int> a = {2, 6, 3, 5, 1, 7};
    int num = 5;
    solve(a, num);
    for (auto el : a)
        cout << el << " ";
    return 0;
}

Answer 1

在使用链表时，交换的概念对于链表来说并不是很有用。相反，您会移动个节点。

这是一个可能的实现：

#include <iostream>

class Node {
    public:
    int value;
    Node * next;
    
    Node(int value, Node * next) {
        this->value = value;
        this->next = next;
    }

    Node(int value) {
        this->value = value;
        this->next = nullptr;
    }

    void print() {
        Node * node = this;
        while (node != nullptr) {
            std::cout << node->value << " -> ";
            node = node->next;
        }
        std::cout << "NULL\n";
    }

    Node * partition(int pivot) {
        if (this->next == nullptr) return this; // Quick exit
        Node * preHead = new Node(0); // Dummy
        Node * preMid = new Node(0, this); // Dummy
        Node * lessTail = preHead;
        Node * prev = preMid;
        while (prev->next) {
            Node * curr = prev->next;
            if (curr->value < pivot) {
                prev->next = curr->next; // remove curr
                lessTail->next = curr; // insert curr
                lessTail = curr; 
            } else {
                prev = curr; // keep curr where it is
            }
        }
        lessTail->next = preMid->next;
        delete preMid;
        Node * head = preHead->next;
        delete preHead;
        return head;
    }
};

int main() {
    // Construct the list from example #2
    Node * head = new Node(1,
                new Node(4,
                new Node(2,
                new Node(5,
                new Node(3)))));
    head->print();  // 1 -> 4 -> 2 -> 5 -> 3 -> NULL
    head = head->partition(4);
    head->print();  // 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    // ...    
}

此代码使用了两个临时节点实例，因为这使代码更容易一些。但也可以在没有这些虚拟节点的情况下进行。在那种情况下，您必须执行一些空指针检查以查看何时分配给 next 属性或 head 变量。

给定一个数组 'a' 和一个整数 'x'，排列 (就地) 的元素使得所有元素 <x come before all the elements >='x'

Given an array 'a' and an integer 'x', arrange the elements of the (in place) such that all the elements <x come before all the elements >='x'

c++

arrays

algorithm

linked-list