一、题目内容

题目描述

有一整型数组，现在进行全排列组合，获得排列组合后最小的一个数。

输入描述

第一行输入数组个数n，第二行输入n个数。

输出描述

输出组成的最小的数字串。

示例1

输入

5
111 22 33 11 34

输出

11111223334

二、解题思路

首先这个问题是个有序的全排列()，假如我们全排列再比较，当n达到一定数量级时是不可取的，因此，如果我们需要确认数组中每个数的位置，那么可以通过维护一个链表（LinkList）去管理它，初始化一个空的链表，表头值为0，我们将读入的数组（）从小到大排列，遍历数组，将第一个数插入链表，随后依次比较第一个数以后与链表中的值的位置（转换成字符串，通过的比较，判断当前数组中的数在链表LinkList中的位置，然后插入），遍历完成后，输出链表除表头的数据即可。时间复杂度

代码实操

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

class Node {
    public:
        int data;
        Node *next;
};
class LinkList {
    public:
        LinkList();
        int  GetLength();
        void CreateLinkList(int n);
        void InsertElemAtIndex(int data, int n);
        void InsertElemAtEnd(int data);
        void InsertElemAtHead(int data);
        void SolveElem(int data, int index);
        void PrintElem();
    private:
        Node * head;
};

LinkList::LinkList() {
    head = new Node;
    head->data = 0;
    head->next = NULL;
}

int LinkList::GetLength() {
    int count = 0;
    Node *p = head->next;
    while(p != NULL) {
        count++;
        p = p -> next;
    }
    return count;
}

void LinkList::CreateLinkList(int n) {
    Node *pnew, *ptemp;
    ptemp = head;
    if (n < 0) {
        exit(EXIT_FAILURE);
    }
    for(int i = 0; i < n; i++) {
        pnew = new Node;
        pnew -> data = i;
        pnew -> next = NULL;
        ptemp -> next = pnew;
        ptemp = pnew;
    }
}

void LinkList::InsertElemAtEnd(int data) {
    Node *newNode = new Node;
    newNode -> next = NULL;
    newNode -> data = data;
    Node *p = head;
    if (head == NULL) {
        head = newNode;
    } else {
        while(p -> next != NULL) {
            p = p -> next;
        }
        p -> next = newNode;
    }
}

void LinkList::InsertElemAtHead(int data) {
    Node *newNode = new Node;
    newNode -> data = data;
    Node *p = head;
    if (head == NULL) {
        head = newNode;
    }
    newNode -> next = p -> next;
    p -> next = newNode;
}

void LinkList::InsertElemAtIndex(int data, int n) {
    if (n < 1 || n > GetLength()) {
        cout << "越界了" << endl;
    } else {
        Node *ptemp = new Node;
        ptemp -> data = data;
        Node *p = head;
        int i = 1;
        while(n > i) {
            p = p -> next;
            i++;
        }
        ptemp -> next = p -> next;
        p -> next = ptemp;
    }
}

void LinkList::SolveElem(int data, int index) {
    Node *p = head;
    if (p == NULL) {
        cout << "空表" << endl;
        return;
    }
    if (GetLength() == 1 && index == 0) {
        p -> next -> data = data;
        return;
    }
    int i = 1;
    stringstream ss2;
    ss2 << data;
    string s2 = ss2.str();
    string s1, s3;
    p = p -> next;
    for(i = 1; i <= GetLength(); i++) {
        if (p == NULL) return;
        stringstream ss1;
        ss1 << p -> data;
        s1 = ss1.str();
        if (s1 + s2 <= s2 + s1) {
            if (p -> next != NULL) {
                stringstream ss3;
                ss3 << p -> next -> data;
                s3 = ss3.str();
                if (s2 + s3 <= s3 + s2) {
                    InsertElemAtIndex(data, i + 1);
                    break;
                }
            } else {
                InsertElemAtEnd(data);
                break;
            }
        } else {
            InsertElemAtIndex(data, i + 1);
            break;
        }
        p = p -> next;
    }
}

void LinkList::PrintElem() {
    Node *p = head;
    if (p == NULL) {
        cout << "空表" << endl;
    } else {
        p = p -> next;
        while(p -> next != NULL) {
            cout << p -> data;
            p = p -> next;
        }
        cout << p -> data;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int a[100010];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a+n);
    LinkList l;
    l.CreateLinkList(1);
    for(int i = 0; i < n; i++) {
        l.SolveElem(a[i], i);
    }
    l.PrintElem();
    cout << endl;
    return 0;
}

说在最后

这道题是我在一次面试中遇到的，刚上手时脑子秀逗了，一个劲把数组中的整型数字的位数拆出来比较，增加了复杂性！哈哈，我也被自己秀一脸。滑稽.gif，大家加油！