Помощь, необходимая для написания алгоритма

Question

Вот описание проблемы

Учитывая целое число N, напишите функцию, которая возвращает целочисленный массив размера N, содержащий числа от 1 до N в случайном порядке.Каждое число от 1 до N должно появляться один раз и не должно повторяться.

• Каково время работы вашего алгоритма?
• Можно ли улучшить ваш алгоритм?

Например: если вам дано число 4, ваш вывод должен сгенерировать что-то вроде 4213, 2413, 3124 и т. Д.

Недопустимые выходные значения будут 1123, 4444, 244.

Есть идеи по решению проблемы?

Answer 1

Да, это домашняя работа. Я только что закончил написание алгоритма на Java, но использование shuffle Фишера-Йейтса кажется гораздо более эффективным. Спасибо, люди. Ниже моя версия алгоритма.

Collection<Integer> generateNumbers(int n) {
    Collection<Integer> numbers = new HashSet<Integer>();
    Random rand = new Random();
    int max = 0;        
    int min = 0;
    for(int i=0;i<n;i++){
        max=(max*10)+n;
        min=(min*10)+1;
    }
    while(numbers.size()<n){
        int random = rand.nextInt(max-min+1)+min;
        int temp = random;
        boolean good = true;
        Set<Integer> digits = new HashSet<Integer>();
        while(temp>0 && good){
            int reminder = temp%10;
            if(reminder > 0 && reminder <= n ){ 
                digits.add(reminder);
            }else
                good = false;
            temp/=10;
        }       
        if(good && digits.size() == n)
        numbers.add(random);
    }       
    return numbers;
}

Answer 2

То, что вы делаете, это тасование целочисленного массива.

Вот объяснение Кнута перемешивания .

Answer 3

Вот подсказка: посмотрите, что такое Фишер-Йейтс.