Как я могу создать отсортированный список уникальных номеров LogN, где N - заданный размер массива? - PullRequest
Новая
       39

Как я могу создать отсортированный список уникальных номеров LogN, где N - заданный размер массива?

0 голосов
/ 26 сентября 2019

Так что в основном я хочу сгенерировать случайные числа и поместить их в список с заданным размером N. Например,

, это создает отсортированный список, где число уникальных чисел равно примерно N /2 Как я могу изменить это так, чтобы уникальные числа были примерно равны LogN? 

     for (int i = 0; i < N; i++) {
         list.add(i, list.get(i) + new Java.util.Random.nextInt(2);
    }

1 Ответ

0 голосов
/ 26 сентября 2019

Если вам нужен постоянно точный список log(n) уникальных номеров, почему бы не сгенерировать их в первую очередь?Вы можете заполнить массив позже. 

import java.util.Random;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class RandomExample {

 public static void main(String[] args) {
  System.out.println(fillLogNUnique(100, 0, 100));
 }


 public static List <Integer> fillLogNUnique(final int n, final int lowLimit, final int highLimit) {
  final Random random = ThreadLocalRandom.current();

  // Assuming log base 2.0.

  final int requiredUniqueCount = (int) Math.floor(Math.log(n) / Math.log(2.0));
  final List <Integer> uniques = random
        .ints(lowLimit, highLimit)
        .limit(requiredUniqueCount)
        .boxed()
        .collect(Collectors.toList());

  return IntStream
        .range(0, n)
        .map(x -> uniques.get(random.nextInt(uniques.size())))
        .boxed()
        .collect(Collectors.toList());
 }
}

Входные данные: n: количество требуемых случайных чисел, lowLimit: нижние границы для сгенерированных чисел и highLimit: верхняя граница.

Выход для этого: 

[17, 29, 98, 17, 17, 29, 64, 64, 64, 17, 98, 98, 91, 17, 64, 50, 17, 50, 50, 64, 98, 91, 29, 50, 91, 50, 91, 98, 91, 98, 98, 29, 91, 91, 98, 64, 29, 98, 91, 50, 64, 50, 64, 17, 17, 50, 29, 29, 50, 50, 91, 50, 17, 17, 98, 64, 17, 98, 64, 17, 50, 17, 50, 50, 91, 50, 64, 91, 64, 91, 64, 64, 64, 91, 64, 64, 50, 50, 91, 50, 17, 17, 64, 98, 91, 17, 17, 17, 64, 50, 91, 29, 29, 91, 29, 50, 29, 91, 17, 91]

..., который имеет ровно 6, поскольку log(100) с основанием 2 имеет целочисленное значение (с полами), равное 6.

Обратите внимание, что этот ответ для Java> = 8.

...