0

我正在用 C++ 处理一个文本文档，并且对于某些解析，链接列表由作为文档“单词”的重复元素组成。

现在，我需要一种算法来对这个链表进行排序，使重复元素与中间的距离相等，但方向相反。中间元素是MARK元素。

Original Linked List:-
Head-> A-B-A-C-C-D-E-F-E-F-D-B (Size 12)

Processed Linked List:-
Head-> A-B-C-D-E-F-MARK-F-E-D-C-B-A (Size 13 = 12 + MARK)

有任何想法吗 ？

4

3 回答 3

0

如果元素至少重复一次。然后你可以使用下面
的算法算法的复杂度是 O(n) 但在新链表中插入节点将是 O(nlogn)
在每次传递中解析链表从linkedList中拔下当前节点并将它们添加到两个新的链表（一个按升序，另一个按降序），最后将新节点“MARK”添加到升序链表的末尾，现在加入两个新创建的链表。
HashMap 仅用于处理唯一值（意味着不考虑重复项）

以下是相同的 JAVA 代码，我很抱歉我无法提供 C++ 中的代码（因为我不知道 C++ :P）
但我已尝试提供尽可能多的评论，以便您了解
我的想法将列表视为具有头尾
节点的双链表节点具有以下结构

class Node
{
  String data;
  Node next, prev;
}

以下代码具有创建处理后的链表所需的方法和排序功能

public Node getHead()
{
    return this.head;
}

public void setHead(Node n)
{
    this.head = n;
}

public Node getTail()
{
    return this.tail;
}

public void setTail(Node n)
{
    this.tail = n;
}

public void addLast(Node n)
{
    // Adds the node to the last of the list
    // in such a way that the inserted node will
    // be sorted in increasing order
}

public void addFirst(Node n)
{
        // Adds the node to the first of the list
        // in such a way that the inserted node will
        // be sorted in non-increasing order
}

public Node sort(Node head)
{
    Node n = head;
    HashMap<String, Boolean> map = new HashMap<String, Boolean>();
    LinkedList asc = new LinkedList();
    LinkedList des = new LinkedList();

    // Parse the linked list
    while(n!=null)
    {
    if(!map.containsKey(n.data))
    {
            // Remove the n from the Current Linked List
        delete(n);
        map.put(n.data);

        // Add in the new linked List
            asc.addLast(n);
            desc.addFirst(n);

            n = n.next;
    }
    }

    // Add new Node Mark to the end of the asc list
    asc.addLast(new Node("MARK"));

    // Join asc list to the desc list
    asc.getTail().next = desc.getHead();

    // Making head and tail as null as it is now combined with ASC list
    // If you do not do it then it may leads to memory leak
    // in deletion of nodes from processed list
    desc.setHead(null);
    desc.setTail(null);

    // Return the head of new processed list
    return asc.getHead();
}

public void delete(Node n)
{
    if(n==null)
        return;

    if(head==n)
    {
        // If the node to delete is head
        head = head.next;
    }
    else if(head==null)
    {
        // If the node to delete is tail
        tail = tail.prev;
    }
    else
    {
        // If the node to delete is present in the middle
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }
    n.next = n.prev = null;
}

注意
如果值不重复，那么它将创建重复元素，因为每个节点都被添加到两个链表中，最终合并

于 2013-05-09T07:59:04.867 回答
0

如果有偶数，可以按值对列表进行排序，新建一个size+1的列表，在中间添加MARK。

然后：

//Iterate over the list, but process both the original and the duplicate at the same time.
for(i = 0; i < (original_list.size()/2); i++)
{
    //First element
    new_list[i] = original_list[i*2]

    //Duplicate element
    new_list[new_list.size() - i] = original_list[(i*2)+1]
}
于 2013-05-09T04:26:42.753 回答
0

假设列表中的所有元素都只重复一次，您可以使用这种方法。

#include <list>
#include <iterator>
#include <iostream>
#include <algorithm>

int main (int argc, char* argv[])
{
    char data[] = {'A', 'B', 'A', 'C', 'C', 'D', 'E', 'F', 'E', 'F', 'D', 'B'};
    std::list<char> c( data, data + sizeof(data) / sizeof(char) );

    // Remove all duplicates
    c.sort();
    std::list<char>::iterator i = std::unique( c.begin(), c.end() );
    c.resize( std::distance(c.begin(), i) );

    // Add 'M' (or MARK, if we were using strings).
    c.push_back( 'M' );

    // Add all the elements excluding 'M' to the back of the list.
    std::copy( ++c.rbegin(), c.rend(), std::back_inserter(c) );

    return 0;
}

如果某些元素不重复，您还没有给出对输出的期望。因此，我无法为这种情况提供正确的行为。该方法可以通过使用 std::unordered_set (C++11) 或其他一些哈希集（例如 Dinkum 的 stdext::hash_set）来实现 O(n)。

于 2013-05-11T11:55:28.703 回答