Покройте заданный диапазон массива

Question

Я пытаюсь выяснить алгоритм для реализации метода, и мне нужно несколько советов в этом отношении.Я дал массив и диапазон,

A = [1, 15, 30, 40, 50]
range =  10

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

Покрытие означает, что расстояние вы можетедостичь как слева, так и справа с предоставленным диапазоном.Например, если у меня есть точка в 23 и диапазон 5, то я могу достичь 18-23 левой стороны и 23-28 правой стороны.Точки могут покрывать как левую, так и правую стороны заданного диапазона.

В предоставленном массиве результат равен 3. Нам понадобится одна точка в 1, другая в 15 и третья в 40. Iобъясните это ниже,

i. The point at 1 will cover till 10 (1-10)
ii. The point at 15 will cover itself (15)
iii.  The point at 40 will cover left till the 30 and at the right till the 50 (30-40-50)

Пожалуйста, укажите вескую причину, прежде чем пытаться понизить голос.Спасибо.

Answer 1

Если массив отсортирован, можно использовать жадный алгоритм.Я также предполагаю, что все числа на входе положительны.

Рассмотрим следующие шаги:

1. Int cover = -1, points= new array
2. For each element in the array:
   2.1 . If element > cover then:
       2.1.1 cover = element + range - 1 // biggest value that still cover the element
       2.1.2 push to point cover value

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

Сложность : предполагается, что n - это размер входного массива:

Сложность по времени составляет O (n), если массив отсортирован, и O (nlogn), если нет.Сложность пространства равна O (k), когда k - количество точек покрытия, ограниченных n.Если вам нужно только количество точек, то сложность пространства равна O (1)

Если точки можно выбрать только из массива, вы можете изменить алгоритм следующим образом:

1. Int cover = -1, points= new array
2. For each i in the array.length:
    2.1 If array[i] > cover then:
        2.1.1 cover = array[i] //element can cover itself 
        2.1.2 for (j=i+1; array[j] < array[i] + range; j++) // find the largest element who still cover array[i]
            2.1.2.1 cover = array[j] // element in index j cover also index i
        2.1.3 push to point cover value
        2.1.4 add range to cover // to mark for cover after a[j]

Пространственная сложность одинакова.Временная сложность также равна O (n) - поскольку каждый шаг внутреннего цикла (j) выполняет i-цикл, мы не выполняем условие оператора if - поэтому мы остаемся с O (n).

Answer 2

Я запрограммировал алгоритм, предложенный Дэвидом в предыдущем ответе.Код указан ниже,

public static int getMinNumberOfPoints(int R, int[] A) {

    int cover = -1;
    int N = A.length;

    List<Integer> list = new ArrayList<>();

    int count = 0;

    for (int i = 0; i < N; i++) {

        if (A[i] > cover) {

            cover = A[i];

            /*
             * find the largest element who still cover A[i]
             * */
            for (int j = i + 1; j < N && A[i] + R >= A[j]; j++) {
                cover = A[j];
            }

            /*
            * add the cover to keep track for camera placement
            * */
            list.add(cover);
            count++;

            cover += R;
        }
    }

    return count;
}

Answer 3

Я постараюсь сделать его лаконичным, используя Stream API, если получу время: -

public static void main(String[] args) {
    int[] arr = {1, 15, 30, 40, 50};
    int range = 10;
    Map<Integer, Set<Integer>> map = new HashMap<>(arr.length); //maps indexes of elements to the indexes of elements it covers

    for (int i = 0; i < arr.length; i++) {
        for (int j : arr) {
            if (j >= arr[i] - range && j <= arr[i] + range) {
                if (map.get(i) == null) {
                    Set<Integer> set = new HashSet<>();
                    set.add(j);
                    map.put(i, set);
                } else {
                    map.get(i).add(j);
                }
            }
        }
    }
    Set<Integer> mapEntriesToDelete = new HashSet<>();
    for (Map.Entry<Integer, Set<Integer>> e : map.entrySet()) {
        for (Map.Entry<Integer, Set<Integer>> f : map.entrySet()) {
            if (!e.getKey().equals(f.getKey()) && e.getValue().containsAll(f.getValue())) {
                mapEntriesToDelete.add(f.getKey());
            }
        }
    }
    mapEntriesToDelete.forEach(map::remove);
    System.out.println("Points: " + map.size());
    System.out.print("At indexes: ");
    map.keySet().forEach(k -> System.out.print(k + ","));
}

Вывод

Points: 3
At indexes: 0,1,3,