题解

题目难度：简单

知识点：数学问题，排序算法

分析：

本题其实考察的是对数组进行排序，第i只奶牛想要一个1和x[i]之间的整数(其中包含1和x[i])。可以先给x[i]最小的奶牛编号，共有x[ i1 ]种方法，然后给第二小的奶牛编号，由于第一小的奶牛已经占用了一个号码，此时第二小的奶牛有（x[i2]-1）种编号方法，以此类推即可，所以编号方法总数为 x[i1](x[i2]-1)(x[i3]-2)*... 。
该问题为排序问题，给出几种常用的方法：

方法1：利用Arrays工具类中sort()函数进行排序

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());  //奶牛数量

        int[] nums = new int[n];  //奶牛们的编号

        String str = sc.nextLine();
        String[] s = str.split(" ");
        for(int i=0;i<n;i++){
            nums[i] = Integer.parseInt(s[i]);
        }

        // 对数组进行排序
        //1. 利用Java的api对数组进行排序
        Arrays.sort(nums);

        long res = 1;
        for(int i= 0; i<n; i++){
            res=res*(nums[i]-i)%1000000007;
        }
        System.out.println(res);
    }
}

方法2：冒泡排序

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());  //奶牛数量

        int[] nums = new int[n];  //奶牛们的编号

        String str = sc.nextLine();
        String[] s = str.split(" ");
        for(int i=0;i<n;i++){
            nums[i] = Integer.parseInt(s[i]);
        }

        // 对数组进行排序

        // 2. 利用冒泡排序
        bubbleSort(nums);

        long res = 1;
        for(int i= 0; i<n; i++){
            res=res*(nums[i]-i)%1000000007;
        }
        System.out.println(res);
    }

    private static void bubbleSort(int[] nums) {
        if(nums==null || nums.length<1){
            return;
        }

        int len = nums.length;
        for(int i = 0; i < len - 1; i++){
            // 每次都是从下标0位置处开始新一轮的比较
            for(int j = 0; j < len - 1 - i; j++){
                // 升序排序
                if(nums[j]>nums[j+1]){
                    swap(nums,j,j+1);
                }
            }
        }

    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;

    }

}

方法3：选择排序

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());  //奶牛数量

        int[] nums = new int[n];  //奶牛们的编号

        String str = sc.nextLine();
        String[] s = str.split(" ");
        for(int i=0;i<n;i++){
            nums[i] = Integer.parseInt(s[i]);
        }

        // 对数组进行排序

        // 2. 利用选择排序
        selectSort(nums);

        long res = 1;
        for(int i= 0; i<n; i++){
            res=res*(nums[i]-i)%1000000007;
        }
        System.out.println(res);
    }

    private static void selectSort(int[] nums) {
        if(nums==null || nums.length<1){
            return;
        }

        int len = nums.length;
        for(int i = 0; i < len - 1; i++){
            for(int j = i+1; j<len; j++){
                if(nums[i]>nums[j]){
                    swap(nums,i,j);
                }
            }
        }

    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;

    }

}

方法4：插入排序

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());  //奶牛数量

        int[] nums = new int[n];  //奶牛们的编号

        String str = sc.nextLine();
        String[] s = str.split(" ");
        for(int i=0;i<n;i++){
            nums[i] = Integer.parseInt(s[i]);
        }

        // 对数组进行排序

        // 2. 利用插入排序
        insertSort(nums);

        long res = 1;
        for(int i= 0; i<n; i++){
            res=res*(nums[i]-i)%1000000007;
        }
        System.out.println(res);
    }

    private static void insertSort(int[] nums) {
        if(nums==null || nums.length<1){
            return;
        }

        int len = nums.length;
                // 下标从1开始
        for(int i = 1; i < len; i++){
            for(int j = i-1; j >= 0 && nums[j]>nums[i]; j--){

                swap(nums,i,j);

            }
        }        
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;

    }

}

方法5：快速排序

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());  //奶牛数量

        int[] nums = new int[n];  //奶牛们的编号

        String str = sc.nextLine();
        String[] s = str.split(" ");
        for(int i=0;i<n;i++){
            nums[i] = Integer.parseInt(s[i]);
        }

        // 对数组进行排序

        // 2. 利用快速排序
        quickSort(nums,0,nums.length-1);

        long res = 1;
        for(int i= 0; i<n; i++){
            res=res*(nums[i]-i)%1000000007;
        }
        System.out.println(res);
    }

    private static void quickSort(int[] nums, int low, int high) {
        if(low>=high){
            return;
        }

        int index = partition(nums,low,high);
        quickSort(nums, 0, index-1);
        quickSort(nums,index+1,high);

    }

    private static int partition(int[] nums, int low, int high) {
        //直接选择第一个当分隔值，不能通过
        //int key=nums[low];

        // 三个值中选择，增大随机性
        int mid=low+(high-low)/2;
        if(nums[mid]>nums[high]){
            swap(nums,low,high);
        }
        if(nums[low]>nums[high]){
            swap(nums,low,high);
        }
        if(nums[mid]>nums[low]){
            swap(nums,low,high);
        }
        int key=nums[low];

        while(low<high){
            while(nums[high]>=key && high>low){ //从后往前找
                high--;
            }
            swap(nums,low,high); //找到之后值进行交换

            while(nums[low]<=key && high > low){  // 从前半部分向后扫描
                low++;
            }
            swap(nums,low,high); 

        }
        return low;

    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;

    }

}

【注意】影响快排算法的效率是中心值key的选取，如果直接选择第一个或最后一个作为key值，无法在规定时间内完成所有测试