Алгоритм поиска кластеров в двумерном массиве

129

28 сентября 2021, 07:40

Всем привет, в упор не вижу решение задачи. Собственно в чем задача: дан 2-мерный массив целых чисел A[N, M] (1<=N<=1000, 1<=M<=1000, 0<=A[_, _]<=1000). Большинство элементов массива нулевые, но есть небольшие "скопления" рядом расположенных чисел. Рядом расположенными ("соседними") числами будем называть такие, которые отстоят друг от друга на 1 позицию влево, вправо, вверх или вниз (но не по диагонали). Такие скопления ненулевых элементов будем называть "кластерами".

int[][] arr = new int[][]{
{0, 0, 1, 2, 4, 5},
{0, 0, 0, 3, 0, 0},
{0, 0, 0, 6, 0, 7},
{0, 0, 0, 0, 1, 3},
{0, 0, 0, 0, 4, 0},
{0, 0, 0, 0, 2, 0}};

Результат должен быть таким:

Одномерный массив целых чисел, содержащий максимальное значение элементов в каждом кластере. Длина массива - количество кластеров. Массив отсортирован по возрастанию.

Одномерный массив целых чисел, содержащий суммарное значение элементов в каждом кластере. Длина массива - количество кластеров. Массив отсортирован по возрастанию.

Этот алгоритм должен работать с любым двумерным массивом. Подскажите, либо намекните в какую сторону думать.

Answer 1

На быструю руку предлагаю такое решение. Здесь много обходов цикла, но стримы умеют параллелить задачу. По поводу оптимизации решайте сами.

Этот метод не работает с лохматой матрицей. Для того, чтобы это исправить, в методе мейн надо править алгоритм обхода (если , конечно, нужна лохматая матрица)

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
public class TestArray {
    public static void main(String[] args) {
        int[][] arr = new int[][]{
            {0, 0, 1, 2, 4, 5},
            {0, 0, 0, 3, 0, 0},
            {0, 0, 0, 6, 0, 7},
            {0, 0, 0, 0, 1, 3},
            {0, 0, 0, 0, 4, 0},
            {0, 0, 0, 0, 2, 0}};
        ArrayCalculator arrayCalculator = new ArrayCalculator();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                arrayCalculator.addElement(arr[i][j]);
            }
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                arrayCalculator.addElement(arr[j][i]);
            }
        }
        System.out.println(Arrays.toString(arrayCalculator.getMaxNumbArray()));
        System.out.println(Arrays.toString(arrayCalculator.getSumNumbArray()));
    }
}
class ArrayCalculator{
    private final List<PriorityQueue<Integer>> list;    
    private PriorityQueue<Integer> queue;
    ArrayCalculator() {
        this.list = new LinkedList<>();
        this.queue = new PriorityQueue(Comparator.reverseOrder()); 
    }
    public void addElement(int element){
        if (element!=0) queue.add(element);
        else addAndClearQueue();
    }
    private void addAndClearQueue(){
        if (queue.isEmpty()) return;
        if (queue.size()==1) queue.clear();
        else{
            list.add(queue);
            queue = new PriorityQueue(Comparator.reverseOrder());
        }
    }
    public Integer[] getMaxNumbArray(){
        return list.parallelStream()
                .map(q->q.element())
                .sorted(Comparator.naturalOrder())
                .toArray(Integer[]::new);
    }
    public Integer[] getSumNumbArray(){        
        return list.parallelStream()
                .map(q->q.parallelStream().reduce(0, Integer::sum))
                .sorted(Comparator.naturalOrder())
                .toArray(Integer[]::new);
    }
}