0

Всем привет, в упор не вижу решение задачи. Собственно в чем задача: дан 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}};

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

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

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

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

4
  • 1
    Сканируем массив. Нашли не ноль - ищем во все стороны от него. А что должно быть в результате - в вопросе не описано.
    – MBo
    22 окт 2019 в 17:45
  • @MBo Одномерный массив целых чисел, содержащий максимальное значение элементов в каждом кластере. Длина массива - количество кластеров. Массив отсортирован по возрастанию. Одномерный массив целых чисел, содержащий суммарное значение элементов в каждом кластере. Длина массива - количество кластеров. Массив отсортирован по возрастанию. 22 окт 2019 в 17:47
  • "должен работать с любым двумерным массивом" - в этой фразе чувствуется какой-то поросячий подтекст. Что значит "с любым"?
    – user176262
    22 окт 2019 в 18:23
  • @Igor это означает, что должен работать с любым размером массива. Алгоритм должен работать на любых данных. 22 окт 2019 в 18:32

1 ответ 1

0

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

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

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);
    }

}
0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.