UVA299:Train Swapping [JAVA]

題目:Online Judge

Loader Loading…
EAD Logo Taking too long?

Reload Reload document
| Open Open in new tab

題目概要

  • 輸入 N 筆測資。
  • 輸入該筆測資有幾節車廂。
  • 計算出需要交換 X 次才能讓車廂號碼由小到大排序(只能相鄰兩節車廂交換)。

解題技巧

  • 最簡單就是用泡沫排序法,兩兩比較,如果左數比右數大就將兩數交換。
  • 泡沬排序法的時間複雜度為 O(n2),即最差的情況(由大到小排序時)需要 (n * (n-1))/2 輪才能讓所有數字由小到大排列

我曾寫過一篇泡沫排序法的筆記:泡沫排序法(Bubble Sort)

程式碼

import java.util.*;
import static java.lang.System.*;
public class main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int cases = sc.nextInt();
    while (cases-- > 0) {
        int number = sc.nextInt();
        int[]arr = new int[number];
        for(int i = 0; i < number; i++) {
            arr[i] = sc.nextInt();
        }

        int results = 0;
        for(int i = 0; i < arr.length - 1; i++) {
            for(int j = 0; j < arr.length - i - 1; j++) {
                int temp = 0;
                if (arr[j] > arr[j+1]) {
                    temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                    results++;
                }
            }
        }
        System.out.println("Optimal train swapping takes " + results + " swaps.");
    }
  }
};
0 0 評分數
Article Rating
訂閱
通知
guest

0 Comments
在線反饋
查看所有評論