Блог

Вопрос: Задан массив numbers = {2, 7, 8, 5, 1, 6, 3, 9, 4} . Проверьте приведенные ниже условия, оба условия должны быть выполнены.

1. a[i] > a[i-1] или if first element a[i] > a[i 1]
2. a[i] > a[i 1] или если last element a[lastelement] > a[lastelement - 1]

Поэтому:

• 1-я итерация — 8, 6, 9 являются пиковыми значениями. Удалите наименьший элемент. Удалить 6. Новый arr {2, 7, 8, 5, 1, 3, 9, 4}. Вывод Arr — {6}

• 2-я итерация — 8, 9 являются пиковыми значениями. Удалите наименьший элемент. Удалить 8. Новый arr {2, 7, 5, 1, 3, 9, 4}. Вывод Arr — {6, 8}

• 3-я итерация — 7, 9 являются пиковыми значениями. Удалите наименьший элемент. Удалить 7. Новый arr {2, 5, 1, 3, 9, 4}. Вывод Arr — {6, 7, 8}

• 4-я итерация — 5, 9 являются пиковыми значениями. Удалите наименьший элемент. Удалить 5. Новый arr {2, 1, 3, 9, 4}. Вывод Arr — {6, 7, 8, 5}

• 5-я итерация — 2,9 являются пиковыми значениями. Удалите наименьший элемент. Удалить 2. Новый arr {1, 3, 9, 4}. Вывод Arr — {6, 7, 8, 5, 2}

• 6-я итерация — 9 являются пиковыми значениями. Удалите наименьший элемент. Удалить 9. Новый arr {1, 3, 4}. Вывод Arr — {6, 7, 8, 5, 2, 9}

• 7-я итерация — 4 являются пиковыми значениями. Удалите наименьший элемент. Удалить 4. Новый arr {1, 3}. Вывод Arr — {6, 7, 8, 5, 2, 9, 4}

• 8-я итерация — 3 являются пиковыми значениями. Удалите наименьший элемент. Удалить 3. Новый arr {1}. Вывод Arr — {6, 7, 8, 5, 2, 9, 4, 3}

• 9-я итерация — 1 — это пиковые значения. Удалите наименьший элемент. Удалить 1. Новый arr {1}. Вывод Arr — {6, 7, 8, 5, 2, 9, 4, 3, 1}

Вывод: {6, 8, 7, 5, 2, 9, 4, 3, 1}

Мое решение работает, но я ищу оптимизированное решение. Пожалуйста, дайте мне знать.

Вот мой код:

 public int[] findMinimumPeaks(int[] arr){
        List<Integer> list1 = new ArrayList<Integer>(arr.length);
        int[] output = new int[arr.length];
        for(int i: arr)
            list1.add(i);
        
        for(int i =0; i<arr.length; i  ){
            int minIndex = minimumPeakElement(list1);
            output[i] = list1.get(minIndex);
            list1.remove(minIndex);
        }
        return output;
    }
    
    public int minimumPeakElement(List<Integer> list1){
        int minIndex = 0, peakStart = Integer.MAX_VALUE, peakEnd = Integer.MAX_VALUE;
        int peak = Integer.MAX_VALUE, minPeak = Integer.MAX_VALUE;
        
        if(list1.size() >= 2){
            if(list1.get(0) > list1.get(1)) peakStart = list1.get(0);
            if(list1.get(list1.size() - 1) > list1.get(list1.size() - 2)) peakEnd = list1.get(list1.size() - 1);
            if(peakStart < peakEnd){
                minPeak = peakStart;
                minIndex = 0;
            }
            else if(peakEnd < peakStart){
                minPeak = peakEnd;
                minIndex = list1.size() - 1;
            }
        }
        
        for(int i=1; i<list1.size() - 1; i  ){
            if(list1.get(i) > list1.get(i   1) amp;amp; list1.get(i) > list1.get(i-1)) peak = list1.get(i);
            if(peak < minPeak){
                minPeak = peak;
                minIndex = i;
            } 
        }
        return minIndex;
    }
  

Вот идея, как оптимизировать асимптотическую сложность.

Используйте одиночный проход по элементам вашего исходного массива, чтобы разделить его на «вверх-вниз», «склоны» или «холмы», то есть подпоследовательность элементов в порядке возрастания, за которой следует подпоследовательность в порядке убывания.

Сохраните эти наклоны в следующей структуре данных:

 val slopes = MinPriorityQueue<Slope>()

class Slope(
 var first: Int, // first element of the slope
 var last: Int,   // last element of the slope
 var peak: Int,   // max or peak element
 var els: MaxPriorityQueue<Int>(),  // all elements of the slope
 var prev: Slope?,    // link to the previous slope in the list or null if first
 var next: Slope?     // link to the next slope in the list or null if last
)

  

Наклоны должны быть сопоставимы по их peak значению.

Теперь, имея эту структуру данных, вы можете poll определить наклон, который имеет минимальное пиковое значение в O(log(N)) . После того, как вы опросили наклон, вам следует обновить наклон, удалив его пиковый элемент (т. Е. Опросить els , затем обновить first , last , peak ), кроме того, наклон может стать пригодным для объединения с предыдущим или следующим наклоном:

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

• Начальное построение структуры данных: O(n log(n))
• Опрос элементов с сохранением наклонов: O(n log (n))
• Общая сложность: O(n log(n))

Примечания:

1. Один из угловых случаев, если в массиве могут быть повторяющиеся элементы, тогда становится els внутренняя приоритетная очередь ( MaxPriorityQueue<Pair<Int,Int>> ), т. Е. Вам нужно сохранить количество потенциально повторяющихся элементов вместе со значением элемента.

2. MinPriorityQueue и MaxPriorityQueue является абстрактной структурой данных на основе кучи с минимальным и максимальным элементом во главе соответственно. Может быть реализован с помощью PriorityQueue в Java