Как создать список случайных чисел без дубликатов?

Question

Мне нужно создать случайные числа, которые будут проходить через массив без дубликатов.

Проблема является дублированием и я не могу использовать любого из утилитов кроме Scanner для ввода (инструкции учителя), как java.util.Random или java.util.ArrayList.

Я использую функцию под названием random, которую мой учитель написал нам, и функция newNum(int num) - это то, где мне нужно то, что я задал, - случайные числа.

package exercise; 

import java.util.Scanner; 

public class Bingo { 

    static int size = 10; 
    static int num; 
    static int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
    private static Scanner sc; 

    public static void main(String[] args) { 

     System.out.print("Press Enter to start: "); 
     sc = new Scanner(System.in); 
     sc.nextLine(); 
     System.out.println(""); 

     // int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
     // int[] tempArray = arr; 

     int num = random(); 
     // int num = sc.nextInt(); 

     // System.out.println(num); 

     while (size > 0) { 
      System.out.println(num); 
      size--; 
      newArray(num); 
      num = random(); 
      newNum(num); 
      // System.out.println(num); 
     } 

    } 

    public static int random() { 

     int max = 10; 
     double r = Math.random(); 
     int num = (int) (r * max + 1); 

     return num; 
    } 

    public static int newNum(int num) { 

     // Here should go the code for the function for getting only new 
     // random number without duplications 

     return num; 
    } 

    public static int newArray(int num) { 

     int[] tempArray = arr; 

     arr = new int[size]; 

     int x = num - 1; 
     for (int i = 0; i < x; i++) { 
      if (i < size) { 
       arr[i] = tempArray[i]; 
      } 
     } 
     for (int i = num; i < size; i++) { 
      if (i < size) { 
       int y = i - 1; 
       arr[y] = tempArray[i]; 
      } else { 
       int a = size - 1; 
       arr[a] = tempArray[size]; 
      } 
     } 
     return num; 
    } 

} 

Answer 1

Прежде всего, вы пишете, что вы не можете использовать перетасовать, но это не значит, что вам запрещено его реализации. На самом деле это не так сложно.

Если вы хотите сделать это, используйте перетасовать Fisher-Yates, как найти на википедии: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

(кстати, так как вы собираетесь в школу, если вы найдете такую ​​статью в Википедии - или любой другая статья - чтобы быть интересной, вы могли бы предложить своему учителю провести эссе по этому поводу, легко получить дополнительный хороший класс)

Конечно, это предполагает, что у вас есть вектор для тасования, который неэффективен для больших векторов («случайные числа в пределах от нуля до одного миллиарда»). В этом случае вы можете пойти с:

Чтобы найти п случайных чисел в пределах 0..M

1. Initialize an empty list of already used random numbers which is ordered, called "numbers" 
2. for i = 0..n-1 
     2a: r = random(0..m-i) (uniform distribution) 
     2b: for every entry in numbers 
      if entry <= r, r++ 
     2c: sort r into numbers (maybe by using a single bubblesort step) 

Это сдвигает сложность от размера вектора, как и раньше на сумму сгенерированных чисел.

Пояснение: На каждой итерации мы хотим найти неиспользованное число. Мы найдем r-е неиспользуемое число (в итерации i) существует диапазон 0..m-i неиспользуемых чисел. Теперь нам нужно только выяснить, какое число является первым неиспользованным. Это делается внутренней итерацией. Нам нужны числа для сортировки из-за этого примера: текущее состояние: numbers = {5, 1}, r = 4. r < 5 -> ничего не делать. r> = 1 -> r ++. Закончите с r = 5, получив двойную запись.

Если сортировка не нужна для результирующего списка, просто используйте два списка.