閱讀340 返回首頁    go 阿裏雲 go 技術社區[雲棲]

龐果網之數組排序

題目詳情

本題來自caopengcs，隻要你有興趣，每個人都可以出題（出題入口在主頁右側邊欄“貢獻題目”->“我要發布”內），以下是題目詳情：

給定一個包含1-n的數列，我們通過交換任意兩個元素給數列重新排序。求最少需要多少次交換，能把數組排成按1-n遞增的順序，其中，數組長度不超過100。

例如：

原數組是3,2,1， 我們隻需要交換1和3就行了，交換次數為1，所以輸出1。

原數組是2,3,1，我們需要交換2和1，變成1,3,2，再交換3和2，變為1，2，3，總共需要的交換次數為2，所以輸出2。


/*********************************
*   日期：2013-11-03
*   作者：SJF0115
*   題號: 題目 數組排序
*   來源：https://hero.pongo.cn/Question/Details?ID=94&ExamID=92
*   結果：AC
*   來源：龐果網
*   總結：
**********************************/
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std; 

int run(const int *a,int n){
    int i,j,count=0;
    int *num = new int[n];  
    num = (int*)a;
    //每一次選一個最小的和待選序列交換
    for(i = 0;i < n;i++){
        //選擇一個最小的
        int min = i;
        for(j = i+1;j < n;j++){
            if(num[min] > num[j]){
                min = j;
            }
        }
        //最小值和待選序列第一個值交換
        if(num[min] != num[i]){
            int temp;
            temp = num[min];
            num[min] = num[i];
            num[i] = temp;
            count++;
        }
    }
    return count;
}
//start 提示：自動閱卷起始唯一標識，請勿刪除或增加。
int main()
{   
    int n = 3;
    int num[4] = {3,2,1}; 
    printf("%d\n",run(num,n));
    return 0;
} 
//end //提示：自動閱卷結束唯一標識，請勿刪除或增加。


最後更新：2017-04-03 14:54:03

  上一篇：go Linux下GPRS撥號功能的實現
  下一篇：go ubuntu下軟件安裝和卸載