package com;

/**
 * 給定一個數列,
 * 判斷最後能不能拿到一個非遞減的數列，若可以回傳true,若不行回傳false。
 * 可以使用0或1次的swap來達到目的。
 *
 * 結果: 62% correctness
 *
 * @author sam
 *
 */

public class Tom_01 {
    public static void main(String[] args){
        int[] A = {1, 5, 3, 3, 7}; // true
        int[] B = {1, 3, 5, 3, 4}; // false
        int[] C = {1, 5, 3, 3, 3, 3, 3, 7}; // true
        int[] D = {-1, 5, 3, 3, 3, 3, 2, 7}; // true
        int[] E = {-1, 5, 3, 3, 3, 2, 3, 7}; // false
        int[] F = {1, 1, 1, 1, 1}; // false
        int[] G = {2, 2, 1, 1, 1}; // false
        int[] H = {2, 1, 1, 1, 1}; // true
        // ? 負數
        Tom_01 question01 = new Tom_01();
//      System.out.println("result: " + question01.solution(A));
//      System.out.println("result: " + question01.solution(B));
//      System.out.println("result: " + question01.solution(C));
//      System.out.println("result: " + question01.solution(D));
//      System.out.println("result: " + question01.solution(E));
//      System.out.println("result: " + question01.solution(F));
//      System.out.println("result: " + question01.solution(G));
//      System.out.println("result: " + question01.solution(H));
    }

    public boolean solution(int[] ary) {
        // check if it's already sorted (not decreasing (= or >))
        boolean isSorted = true;
        int index_wrong_one = -1;
        for (int i = 0; i < ary.length - 1; i++) { // attention: do not let i+1 exceed the length
            if (ary[i] > ary[i + 1]) {
                isSorted = false;
                index_wrong_one = i;
                break;
            }
        }

        // if not , get the one the needs to be swapped
        int index_smallest_to_swap = -1;
        int smallest_to_swap = Integer.MAX_VALUE;
        if (!isSorted) {
            // find the smallest one after the wrong one in terms of index
            for (int i = index_wrong_one + 1; i < ary.length; i++) {
                if (ary[i] <= smallest_to_swap) {
                    smallest_to_swap = ary[i];
                    index_smallest_to_swap = i;
                }
            }
        }else {
//          System.out.println("end 01 true");
            return true; // it's sorted already
        }

        // actually swap them
        int tmp_wrong_one = ary[index_wrong_one];
        ary[index_wrong_one] = ary[index_smallest_to_swap];
        ary[index_smallest_to_swap] = tmp_wrong_one;

        // check if it's already sorted again
        isSorted = true;
        for (int i = 0; i < ary.length - 1; i++) {
            if (ary[i] > ary[i + 1]) {
                isSorted = false;
            }
        }

        if (isSorted) {
            return true; // it's sorted after one swap
        }

        return false; // it's not sorted even after one swap
    }
}