iT邦幫忙

1

【zerojudge惡龍題】- e446: 排列生成,你知道其實一直printf很耗時嗎?

題目分享: e446: 排列生成

這一題很有意思,
我覺得它雖然放在基礎題庫中,
但演算法本身和I/O優化都很有挑戰

題意: 生出1∼N所有的排列(N最大=10)。
譬如輸入3,要輸出

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

窮舉數字的排列是一個很經典的問題,
leetcode的第46,47題也是這個問題,
因此演算法本身容易找到教學
本文便不特別聊這一塊,
主要聊聊I/O優化的部分

首先,如果把leetcode上的解答直接搬過來用(先把所有排列存成vector<vector<int>>再印出來),
那這樣保證超時,
應該一組答案排完時立即印出答案。
至於要怎麼印也有點學問。

解法一、scanf, print(6.1秒, AC)

這一題雖不好做,但好在時間限制上還算寬鬆,
在最大的測資只要10秒內執行完就過關,
一開始我用cin, cout超時了,
改成scanf, print就過關了,
但也需要6.1秒的時間

#include <iostream>
#include <vector>
using namespace std;


void permuteDFS(vector<int> nums, int start) {
    if (start == nums.size()){
        for(auto i: nums){
            printf("%d ",i);
        }
        printf("\n");
    } 
    for (int i = start; i < nums.size(); ++i) {
        //用swap使所有元素都能列於相對的第一位置上
        swap(nums[start], nums[i]);   
        permuteDFS(nums, start + 1);
    }
}


int main() {
    int n;
    scanf("%d", &n);
    vector<int> nums;
    for(int i = 1; i<=n;i++){
        nums.push_back(i);
    }
    permuteDFS(nums, 0);
    return 0;
}

解法二、用char array存答案再印出(1.3秒, AC)

實測的結果相當顯著,
從一個一個數字的印,
改成將結果存在字串陣列再一次印出,
效率快了將近5倍左右。

#include <iostream>
#include <vector>
using namespace std;

char ans[100];

void permuteDFS(vector<int> nums, int start) {
    if (start == nums.size()){
        char *pc = ans;
        for(auto i: nums){
            if(i<10){
                *pc++ = '0'+i;
            }
            else{
                *pc++ = '1';
                *pc++ = '0';
            }
            *pc++ = ' ';
        }
        *pc = '\0'; //結束字元
        printf("%s\n", ans);
    } 
    for (int i = start; i < nums.size(); ++i) {
        //用swap使所有元素都能列於相對的第一位置上
        swap(nums[start], nums[i]);   
        permuteDFS(nums, start + 1);
    }
}


int main() {
    int n;
    scanf("%d", &n);
    vector<int> nums;
    for(int i = 1; i<=n;i++){
        nums.push_back(i);
    }
    permuteDFS(nums, 0);
    return 0;
}

尚未有邦友留言

立即登入留言