Как исправить и доработать алгоритм для работы с массивами
Я решал задачу на массивы: Вводится массив целых чисел. Найти наиболее длинную подпоследовательность подряд идущих элементов такую, что все элементы данной подпоследовательности равные за исключением 2-х произвольных элементов (реализовать функцию, которая будет возвращать позицию первого элемента такой подпоследовательности и кол-во элементов). В случае нескольких таких подпоследовательностей найти самую первую. Например, для массива {4, 5, 3, 3, 7, 3, 3, 7, 6, 4, 6, 7, 7, 7, 7, 1} правильным ответом будет { 5, 3, 3, 7, 3, 3 } (также существует еще три таких подпоследовательности длиной 6 – {3, 3, 7, 3, 3, 7},{4, 6, 7, 7, 7, 7} и {6, 7, 7, 7, 7, 1}).
Разработал алгоритм, он работает, но не совсем правильно, так как цикл, перемещающий нижний индекс работает не правильно, как его пофиксить?
сам код
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static int[] InputArray(){
System.out.print("Enter the number of elements of the array: ");
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] numbers = new int[n];
for (int i = 0; i < n; i++){
System.out.printf("Enter element %s: ", i+1);
int e = scan.nextInt();
numbers[i] = e;
}
return numbers;
}
public static void OutputArray(int[] array){
}
public static int[] solution(int[] array){
int n = array.length;
if (n < 3) {
return null; // Невозможно найти такую подпоследовательность
}
int r = 1;
int l = 0;
int m = 0;
int maxIndex = 0;
int minIndex = 0;
int counter = 0; //переменная считающая сколько следующих элементов равны первому
элементу
while (r < n) {
if (array[r] == array[l]){
counter++;
}
while (r - l - counter + 1 > 3) { // сам проблемный цикл
l++;
if (array[r] == array[l]){
counter--;
}
}
if (counter >= 2){
if ((r - l - counter + 1 == 3) && (r - l > maxIndex - minIndex)) {
maxIndex = r;
minIndex = l;
}
}
r++;
}
return Arrays.copyOfRange(array, minIndex, maxIndex + 1);
}
public static void main(String[] args) {
int[] array = InputArray();
int[] array2 = solution(array);
System.out.print(Arrays.toString(array2));
}
}
Ответы (1 шт):
Автор решения: Pak Uula
→ Ссылка
Вашу задачу можно решить как минимум двумя способами.
Решение предпросмотром
Например, простым предпросмотром вперёд. Для текущего положения i смотрим вперёд - насколько длинным будет искомый подмассив, если он начнётся в позиции i. Таким образом будут построены все подмассивы, из них выбран наибольший.
import java.util.HashSet;
/**
* Класс Solver1 предоставляет методы для поиска подмассивов с ограниченным
* числом уникальных элементов.</br>
*
* Используется алгоритм "грубой силы", который пробегает по всем значениям
* индексов и предпросматривает подмассивы вперёд, как если бы лучший подмассив
* начинался с текущего индекса.</br>
*
* Константы:
* <ul>
* <li>DEFAULT_UNIQUE_COUNT - значение по умолчанию для uniqueCount.
* </ul>
* Методы:
* <ul>
* <li>matchingEnd(int start): Возвращает индекс конца подмассива, в котором
* содержится не более uniqueCount уникальных элементов.
* <li>bestRange(): Находит и возвращает лучший диапазон в массиве, где число
* уникальных элементов не превышает uniqueCount.
* </ul>
*
* @param arr массив целых чисел, в котором выполняется поиск.
* @param uniqueCount максимальное количество уникальных элементов в подмассиве.
*
*/
public class Solver1 {
/**
* Массив целых чисел, в котором выполняется поиск.
*/
private final Integer[] arr;
/**
* Максимальное количество уникальных элементов в подмассиве.
*/
private final int uniqueCount;
/**
* Значение по умолчанию для uniqueCount.
*/
public static final int DEFAULT_UNIQUE_COUNT = 3;
/**
* Конструктор для создания объекта Solver1.
*
* @param arr массив целых чисел, в котором выполняется поиск.
* @param uniqueCount максимальное количество уникальных элементов в подмассиве.
*/
public Solver1(Integer[] arr, int uniqueCount) {
if (uniqueCount < 1) {
throw new IllegalArgumentException("Unique count should be greater than 0");
}
this.arr = arr;
this.uniqueCount = uniqueCount;
}
/**
* Конструктор для создания объекта Solver1 с uniqueCount по умолчанию.
*
* @param arr массив целых чисел, в котором выполняется поиск.
*/
public Solver1(Integer[] arr) {
this(arr, DEFAULT_UNIQUE_COUNT);
}
/**
* Находит и возвращает лучший диапазон в массиве.</br>
* Лучший диапазон определяется как самый длинный подмассив,
* в котором число уникальных элементов не превышает uniqueCount.
*
* @return объект Range, представляющий лучший диапазон в массиве.
*/
public Range bestRange() {
Range best = new Range(0, 0);
for (int i = 0; i < arr.length - best.len(); i = skipSameVal(i)) {
var end = matchingEnd(i);
if (end - i > best.len()) {
best = new Range(i, end);
}
}
return best;
}
/**
* Возвращает индекс конца подмассива, в котором содержится не более uniqueCount
* уникальных элементов.
* Подмассив начинается с индекса start.
*
* @param start начальный индекс для поиска.
* @return индекс первого элемента после конца искомого подмассива.
* @throws IndexOutOfBoundsException если start находится вне массива.
*/
public int matchingEnd(int start) {
if (start < 0 || start >= arr.length) {
throw new IndexOutOfBoundsException();
}
var numbers = new HashSet<Integer>(); // Множество уникальных элементов подмассива.
numbers.add(start);
for (var i = skipSameVal(start) ; i < arr.length; skipSameVal(start)) {
var v = arr[i];
if (numbers.contains(v)) {
// Этот элемент уже есть в подмассиве
continue;
}
if (numbers.size() == uniqueCount) {
// Подмассив должен содержать не более uniqueCount уникальных элементов.
// Добавление текущего элемента приведёт к превышению лимита.
return i;
}
// Добавляем текущий элемент в множество уникальных элементов.
numbers.add(v);
}
return arr.length;
}
/**
* Пропускает элементы массива с одинаковыми значениями, начиная с указанного индекса.
*
* @param start начальный индекс для проверки.
* @return индекс первого элемента, который отличается от элемента на позиции start,
* или длину массива, если все последующие элементы одинаковы.
*/
private int skipSameVal(int start) {
var v = arr[start];
for (int i = start + 1; i < arr.length; i++) {
if (arr[i] != v) {
return i;
}
}
return arr.length;
}
}
Сложность решения порядка n^2, где n - размер массива.
Решение без предпросмотров
В этом решении тянется список из уже просмотренных диапазонов одинаковых чисел. В списке поддерживается инвариант - число уникальных элементов из диапазонов, хранящихся в списке, не превышает заданное (в вашем случае 3). Если добавляется диапазон с четвёртым уникальным элементом, диапазоны из головы списка отбрасываются, чтобы выполнить инвариант.
/**
* Класс Solver2 предоставляет методы для поиска подмассивов с ограниченным
* числом уникальных элементов.</br>
*
* Для поиска подмассива максимальной длины алгоритм делает один проход.
* Хранится список диапазонов одинаковых значений.</br>
*
* Константы:
* <ul>
* <li>DEFAULT_UNIQUE_COUNT - значение по умолчанию для uniqueCount.
* </ul>
* Методы:
* <ul>
* <li>bestRange(): Находит и возвращает лучший диапазон в массиве, где число
* уникальных элементов не превышает uniqueCount.
* </ul>
*
* @param arr массив целых чисел, в котором выполняется поиск.
* @param uniqueCount максимальное количество уникальных элементов в подмассиве.
*
*/
public class Solver2 {
/**
* Массив целых чисел, в котором выполняется поиск.
*/
private final Integer[] arr;
/**
* Максимальное количество уникальных элементов в подмассиве.
*/
private final int uniqueCount;
/**
* Значение по умолчанию для uniqueCount.
*/
public static final int DEFAULT_UNIQUE_COUNT = 3;
/**
* Конструктор для создания объекта Solver2.
*
* @param arr массив целых чисел, в котором выполняется поиск.
* @param uniqueCount максимальное количество уникальных элементов в подмассиве.
*/
public Solver2(Integer[] arr, int uniqueCount) {
if (uniqueCount < 1) {
throw new IllegalArgumentException("Unique count should be greater than 0");
}
this.arr = arr;
this.uniqueCount = uniqueCount;
}
/**
* Конструктор для создания объекта Solver2 с uniqueCount по умолчанию.
*
* @param arr массив целых чисел, в котором выполняется поиск.
*/
public Solver2(Integer[] arr) {
this(arr, DEFAULT_UNIQUE_COUNT);
}
/**
* Находит и возвращает лучший диапазон в массиве.</br>
* Лучший диапазон определяется как самый длинный подмассив,
* в котором число уникальных элементов не превышает uniqueCount.
*
* @return объект Range, представляющий лучший диапазон в массиве.
*/
public Range bestRange() {
if (arr.length == 0) {
return new Range(0, 0);
}
NRangeList ranges = new NRangeList(uniqueCount);
Range maxRange = new Range(0, 0);
for (int i = skipSameVal(0); i < arr.length; i = skipSameVal(i)) {
var prev = arr[i-1];
ranges.add(prev, i);
if (ranges.len() > maxRange.len()) {
maxRange = new Range(ranges.start(), ranges.end());
}
}
ranges.add(arr[arr.length-1], arr.length);
if (ranges.len() > maxRange.len()) {
maxRange = new Range(ranges.start(), ranges.end());
}
return maxRange;
}
/**
* Пропускает элементы массива с одинаковыми значениями, начиная с указанного
* индекса.
*
* @param start начальный индекс для проверки.
* @return индекс первого элемента, который отличается от элемента на позиции
* start,
* или длину массива, если все последующие элементы одинаковы.
*/
private int skipSameVal(int start) {
var v = arr[start];
for (int i = start + 1; i < arr.length; i++) {
if (arr[i] != v) {
return i;
}
}
return arr.length;
}
}
Поддержание инварианта в списке диапазонов возложено на класс NRangeList:
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* Класс NRangeList представляет собой список диапазонов одинаковых чисел,
* идущих подряд в массиве.
*
* Он позволяет добавлять новые диапазоны, проверять, пуст ли список, обрезать
* список до максимального количества уникальных значений,
* а также получать начальную и конечную позиции диапазонов и их суммарную
* длину.
*
* Пример использования:
*
* <pre>
* NRangeList nRangeList = new NRangeList(3);
* nRangeList.add(1, 5); // число 1 повторяется 5 раз
* nRangeList.add(2, 10); // число 2 повторяется 5 раз
* nRangeList.add(3, 15); // число 3 повторяется 5 раз
* nRangeList.add(4, 20); // Список будет обрезан до 3 уникальных значений
* </pre>
*/
public class NRangeList {
/**
* Список объектов диапазонов значений.
*/
private List<NRange> nRanges;
/**
* Множество уникальных значений N.
*/
private Set<Integer> cache = new HashSet<Integer>();
/**
* Максимальное количество уникальных элементов.
*
* Если при добавлении очередного диапазона количество уникальных значений превысит это значение,
* список диапазонов будет обрезан до максимального количества уникальных значений.
*/
public final int MAX_UNIQUE_COUNT;
/**
* Конструктор для создания списка диапазонов.
*
* @param uniqueCount максимальное количество уникальных значений N
*/
public NRangeList(int uniqueCount) {
if (uniqueCount < 1) {
throw new IllegalArgumentException("Unique count should be greater than 0");
}
MAX_UNIQUE_COUNT = uniqueCount;
nRanges = new java.util.ArrayList<>();
}
/**
* Проверяет, пуст ли список диапазонов.
*
* @return true, если список пуст, иначе false
*/
public boolean isEmpty() {
return nRanges.isEmpty();
}
/**
* Обрезает список диапазонов до максимального количества уникальных значений N.
*
* @return true, если список был обрезан, иначе false
*/
public boolean truncate() {
if (cache.size() <= MAX_UNIQUE_COUNT) {
return false;
}
var set = new HashSet<Integer>();
for (int i = nRanges.size() - 1; i >= 0; i--) {
var r = nRanges.get(i);
if (set.contains(r.N)) {
continue;
}
if (set.size() < MAX_UNIQUE_COUNT) {
set.add(r.N);
continue;
}
nRanges.subList(0, i + 1).clear();
cache = set;
return true;
}
throw new AssertionError("Should not reach here");
}
/**
* Добавляет новый диапазон в список. Диапазон начинается с последнего диапазона
* в списке.
*
* Если при добавлении нового диапазона дисло уникальных значений N превышает
* максимальное количество,
* список диапазонов обрезается до максимального количества уникальных значений
* N.
*
* @param N число, которое повторяется в диапазоне
* @param end конечная позиция диапазона
* @return true, если список был обрезан после добавления, иначе false
*/
public boolean add(Integer N, int end) {
if (end <= this.end()) {
throw new IllegalArgumentException("Range end is not greater than the last range end");
}
cache.add(N);
nRanges.add(new NRange(N, end(), end));
return truncate();
}
/**
* Возвращает начальную позицию первого диапазона в списке.
*
* @return начальная позиция первого диапазона, или 0, если список пуст
*/
public int start() {
if (isEmpty()) {
return 0;
}
return nRanges.getFirst().range.start;
}
/**
* Возвращает конечную позицию последнего диапазона в списке.
*
* @return конечная позиция последнего диапазона, или 0, если список пуст
*/
public int end() {
if (isEmpty()) {
return 0;
}
return nRanges.getLast().range.end;
}
/**
* Возвращает суммарную длину диапазонов из списка.
*
* @return длина диапазона
*/
public int len() {
return end() - start();
}
/**
* Внутренний класс NRange представляет диапазон одинаковых чисел, идущих подряд
* в массиве.
*/
private static class NRange {
/**
* Число, которое повторяется в диапазоне.
*/
public final Integer N;
/**
* Диапазон индексов массива.
*/
public final Range range;
/**
* Конструктор для создания диапазона NRange.
*
* @param n уникальный идентификатор диапазона
* @param start начальная позиция диапазона
* @param end конечная позиция диапазона
*/
public NRange(Integer n, int start, int end) {
N = n;
range = new Range(start, end);
}
/**
* Возвращает строковое представление объекта NRange.
*
* @return строковое представление объекта NRange
*/
@Override
public String toString() {
return "NRange{" + "N=" + N + ", range=" + range + '}';
}
}
}
Полное решение здесь: https://github.com/pakuula/StackOverflow/tree/main/java/1602165