Как получить все n наборов из трех последовательных элементов в массиве или массиве с оператором for? - PullRequest
Новая
       8

Как получить все n наборов из трех последовательных элементов в массиве или массиве с оператором for?

0 голосов
/ 30 апреля 2010

Я пытаюсь использовать подход с выпуклой оболочкой, и маленькая проблема в том, что мне нужно получить все наборы из трех последовательных вершин, например: 

private void isConvexHull(Ponto[] points) {
        Arrays.sort(points);
        for (int i = 0; i <points.length; i++) {
            isClockWise(points[i],points[i+1],points[i+2]);
        }
     //... 
    }

Я всегда делаю то, что не считаю чистым кодом. Не могли бы вы помочь мне найти один или несколько путей к этому? Я хочу, чтобы он был круглым, т.е. если моя первая точка набора является последним элементом в массиве, 2-й элемент будет 3-м в списке, а 3-й в этом наборе будет 2-й элемент в списке , и так далее. Они должны быть подряд, вот и все.

Ответы [ 2 ]

5 голосов
/ 30 апреля 2010

Остаток "трюк"

Вы можете использовать % "трюк" (% - оператор остатка JLS 15.17.3 ) для циклического индексирования. Здесь я проиллюстрирую общую идею, используя вместо этого String. 

    String s = "ABCDE";
    final int L = s.length();
    for (int i = 0; i < L; i++) {
        System.out.format("%c%c%c ",
            s.charAt(i),
            s.charAt((i + 1) % L),
            s.charAt((i + 2) % L)
        );
    } // prints "ABC BCD CDE DEA EAB "

Ан Iterator подход

Однако, если вы часто выполняете эту триплетную обработку, в целом будет лучше иметь Iterator<PointTriplet> или что-то подобное.

Вот прототип, иллюстрирующий идею: 

import java.util.*;

public class CircSubArray {
    static <T> Iterator<T[]> circularIterator(final T[] arr, final int K) {
        return new Iterator<T[]>() {
            int index = 0;
            final int L = arr.length;
            T[] sub = Arrays.copyOf(arr, K); // let it do the dirty work!

            @Override public boolean hasNext() {
                return index < L;
            }
            @Override public T[] next() {
                for (int i = 0; i < K; i++) {
                    sub[i] = arr[(index + i) % L];
                }
                index++;
                return sub; // we always overwrite; no need to .clone()
            }
            @Override public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }   
    public static void main(String[] args) {
        String[] arr = { "s1", "s2", "s3", "s4", "s5", "s6" };

        Iterator<String[]> iter = circularIterator(arr, 4);
        while (iter.hasNext()) {
            System.out.println(Arrays.toString(iter.next()));
        }
    }
}

Это печатает: 

[s1, s2, s3, s4]
[s2, s3, s4, s5]
[s3, s4, s5, s6]
[s4, s5, s6, s1]
[s5, s6, s1, s2]
[s6, s1, s2, s3]

A List решение на основе

Как говорит Effective Java 2nd Edition , пункт 25: Предпочитать списки массивам. Вот решение, которое избыточно хранит первые K-1 элементов в конце List, а затем просто использует subList, чтобы получить K элементов одновременно. 

    String[] arr = { "s1", "s2", "s3", "s4", "s5", "s6" };

    final int L = arr.length;
    final int K = 3;
    List<String> list = new ArrayList<String>(Arrays.asList(arr));
    list.addAll(list.subList(0, K-1));

    for (int i = 0; i < L; i++) {
        System.out.println(list.subList(i, i + K));
    }

Это печатает: 

[s1, s2, s3]
[s2, s3, s4]
[s3, s4, s5]
[s4, s5, s6]
[s5, s6, s1]
[s6, s1, s2]

Поскольку subList является представлением, для этого не нужно выполнять смещение O(K), как это делает решение на основе массива. Это также показывает выразительность List над массивами.

2 голосов
/ 30 апреля 2010

Просто запомните предыдущие две точки, начиная с конца, и сдвигайте их с каждой итерацией. 

private static boolean isConvexHull(Ponto[] points)
{
    final int len = points.length;
    if (len < 3) return false;
    Arrays.sort(points);

    Ponto p1 = points[len - 2];
    Ponto p2 = points[len - 1];
    for (Ponto p3 : points)
    {
        if (!isClockWise(p1, p2, p3)) return false;
        p1 = p2;
        p2 = p3;
    }
    return true;
}

Кстати, как именно вы сортируете массив? Что такое критерий сортировки?

...