一、題目內(nèi)容

題目描述

有一整型數(shù)組衰猛，現(xiàn)在進行全排列組合迟蜜，獲得排列組合后最小的一個數(shù)。

輸入描述

第一行輸入數(shù)組個數(shù)n啡省，第二行輸入n個數(shù)娜睛。

輸出描述

輸出組成的最小的數(shù)字串髓霞。

示例1

輸入

5
111 22 33 11 34

輸出

11111223334

二、解題思路

首先這個問題是個有序的全排列()畦戒，假如我們?nèi)帕性俦容^方库，當n達到一定數(shù)量級時是不可取的，因此障斋，如果我們需要確認數(shù)組中每個數(shù)的位置纵潦，那么可以通過維護一個鏈表（LinkList）去管理它，初始化一個空的鏈表垃环，表頭值為0邀层，我們將讀入的數(shù)組（）從小到大排列，遍歷數(shù)組遂庄，將第一個數(shù)插入鏈表寥院，隨后依次比較第一個數(shù)以后與鏈表中的值的位置（轉換成字符串，通過的比較涛目，判斷當前數(shù)組中的數(shù)在鏈表LinkList中的位置秸谢，然后插入），遍歷完成后霹肝，輸出鏈表除表頭的數(shù)據(jù)即可估蹄。時間復雜度

代碼實操

#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;
}

說在最后

這道題是我在一次面試中遇到的，剛上手時腦子秀逗了沫换，一個勁把數(shù)組中的整型數(shù)字的位數(shù)拆出來比較元媚，增加了復雜性！哈哈苗沧，我也被自己秀一臉√可梗滑稽.gif待逞，大家加油！