package chapter_computational_complexity;

import java.util.*;

public class worst_best_time_complexity {
    /* 生成一个数组，元素为 { 1, 2, ..., n }，顺序被打乱 */
    static int[] randomNumbers(int n) {
        Integer[] nums = new Integer[n];
        // 生成数组 nums = { 1, 2, 3, ..., n }
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        // 随机打乱数组元素
        Collections.shuffle(Arrays.asList(nums));
        // Integer[] -> int[]
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = nums[i];
        }
        return res;
    }

    /* 查找数组 nums 中数字 1 所在索引 */
    static int findOne(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1)
                return i;
        }
        return -1;
    }
    
    /* Driver Code */
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            int n = 100;
            int[] nums = randomNumbers(n);
            int index = findOne(nums);
            System.out.println("\n数组 [ 1, 2, ..., n ] 被打乱后 = " + Arrays.toString(nums));
            System.out.println("数字 1 的索引为 " + index);
        }
    }
}
