Есть ли способ ускорить выполнение в приведенном ниже Java-коде?
Мой код Java, как показано ниже.
boolean almostIncreasingSequence(int[] sequence) {
Integer[] arr = new Integer[sequence.length];
for(int ctr = 0; ctr < sequence.length; ctr++) {
arr[ctr] = Integer.valueOf(sequence[ctr]); // returns Integer value
}
System.out.println("Integer :: " + arr);
List<Integer> al = new ArrayList<Integer>();
// adding elements of array to arrayList.
Collections.addAll(al, arr);
System.out.println("list :: " + al);
int save, flag = 0;
for(int i=0; i<al.size(); i++) {
save = al.get(i);
al.remove(i);
if(al.size()==1) return true;
for(int j=0; j<al.size()-1; j++) {
if(al.get(j+1) > al.get(j)) {
flag = 0;
continue;
}
else {
flag = 1;
break;
}
}
if(flag == 0) {
return true;
}
al.add(i,save);
}
if(flag == 1)
return false;
return true;
}
Код предназначен для задачи "Учитывая последовательность целых чисел в виде массива, определите, можно ли получить строго возрастающую последовательность, удалив не более одного элемента из массива".
Для некоторых тестовых случаев это показывает, что для выполнения этого требуется более 3 секунд. Но я не уверен, где я могу внести изменения, чтобы выполнить их быстрее. У меня нет доступа к тесту.
Здесь я создал 2 цикла for, потому что в первом цикле я создаю список, в котором будет удален каждый индекс, а во втором цикле я перебираю новый список, в котором был удален элемент.
как образец массива {1,2,4,3}, то в первом цикле я создаю массив, который будет {2,4,3},{1,4,3},{1,2,3} и {1,2,4}. Во втором цикле я перебираю все эти 4 массива для сравнения каждого элемента.
4 ответа
Основное наблюдение состоит в том, что список можно разложить на 3 (возможно, пустые) части:
list = list[0..s) + list[s..e) + list[e..length)
куда list[0..s) а также list[e..length) строго увеличивающиеся списки, и list[s..e) это вещи между ними.
Поскольку вы знаете, что эти списки префиксов и суффиксов строго увеличиваются, вам не нужно повторно проверять это свойство в этих списках.
Вы можете выбрать любые значения для s а также e при условии ограничения 0 <= s <= e < length, но предположим, что вы выбираете их так, что s настолько большой, насколько это возможно, и e настолько мал, насколько это возможно.
Если список имеет желаемое общее свойство, то либо:
s == lengthтак что список уже строго увеличивается, ничего не удаляя.list[s..e)имеет длину не более 1 (e-s == 1), а такжеlist[0..s) + list[e..length)строго увеличивается. Вы можете проверить это, просто сравнивlist[s-1] < list[e],list[s..e)пустой (s == e), и поэтому вам требуется либоlist[0..s-1) + list [e..length)(то есть удаление последнего элемента префикса) илиlist[0..s) + list[e+1..length)(т.е. опуская первый элемент суффикса), чтобы быть строго увеличивается. Проверьте(s == 0 || list[s-1] < list[e])а также(e+1 == length || list[s] < list[e+1])соответственно.- Если
list[s..e)имеет более 1 элемента (e-s > 1), вам потребуется удалить более одного элемента, чтобы дать списку желаемое свойство.
Найти s а также e:
Начните с целочисленного указателя s в ноль. Увеличивайте его до тех пор, пока он не достигнет конца или не покажет элемент, list[0..s) это строго растущий список, но list[0..s+1) не может быть.
Начните с целочисленного указателя e в длину списка. Уменьшить это пока e>s а также list[e-1..length) не было бы строго увеличивающегося списка.
Я бы пошел с этим.
Изменить: Предоставлено обновленное решение. Это быстро, но читабельность не очень хорошая. Я также включил класс main() с некоторыми стандартными последовательностями, с которыми я тестировал этот код. (В формате, который тестирующий может легко проверить, чтобы добавить дополнительные случаи).
/**
* Returns true if by removing maximum 1-entry the sequence can be strictly increasing.If not, it returns false. Doesn't check
* if sequence is empty
*/
private static boolean checkIfRemovingMaxOneElementItIsStrictlyIncreasing(final int[] sequence)
{
boolean isFirstNonDecreasingSequence = true;
final int length = sequence.length;
int maxValue = sequence[0];
for (int i = 1; i < length; i++)
{
if (sequence[i] <= maxValue)
{
if (isFirstNonDecreasingSequence == true)
{
if ((i + 1) < length) // check this is not the last element
{
if ((sequence[i - 1] >= sequence[i + 1])) // Check if it is peak or pit
{
// [i-1] is a local peak. Remove [i-1]
if (i > 1)
{
if (sequence[i] <= sequence[i - 2])
{
return false;
}
}
maxValue = sequence[i];
}
// else { // [i] is a local pit. Remove [i]. maxValue is not updated. }
isFirstNonDecreasingSequence = false;
}
}
else
{
return false;
}
}
else
{
maxValue = sequence[i];
}
}
return true;
}
public static void main(final String[] args)
{
final List<int[]> testInputs = new ArrayList<>();
final List<Boolean> correctResults = new ArrayList<>();
final List<Boolean> results = new ArrayList<>();
testInputs.add(new int[] { 0 }); // single-element sequence
correctResults.add(true);
testInputs.add(new int[] { 0, 0 }); // two-element sequence
correctResults.add(true);
testInputs.add(new int[] { 0, 0, 0 }); // constant sequence
correctResults.add(false);
testInputs.add(new int[] { 1, 2, 3, 4, 6 }); // strictly increasing
correctResults.add(true);
testInputs.add(new int[] { 3, 2, 1 }); // strictly decreasing
correctResults.add(false);
testInputs.add(new int[] { 10, 1, 2, 3 }); // first value (10) should be removed
correctResults.add(true);
testInputs.add(new int[] { 1, 2, 3, 1 }); // last value (1) should be removed
correctResults.add(true);
testInputs.add(new int[] { 1, 2, 5, 3, 5 }); // peak (5) (inner value should be removed)
correctResults.add(true);
testInputs.add(new int[] { 1, 2, 3, 10, 4, 4, 5 }); // peak (10) followed by constant (4)
correctResults.add(false);
testInputs.add(new int[] { 1, 2, 3, 1, 4, 6 }); // pit (1) (inner value should be removed)
correctResults.add(true);
testInputs.add(new int[] { 5, 6, 2, 6, 7 }); // pit (2) that does not recover
correctResults.add(false);
testInputs.add(new int[] { 5, 0, 3 }); // first value should be removed
correctResults.add(true);
testInputs.add(new int[] { 5, 6, 1, 2 }); // sequence downward gap (pit)
correctResults.add(false);
for (int i = 0; i < testInputs.size(); i++)
{
results.add(checkIfRemovingMaxOneElementItIsStrictlyIncreasing_NoAssignment(testInputs.get(i)));
if (correctResults.get(i) == results.get(i))
{
System.out.println("Test case: " + i + " successful.");
}
else
{
System.out.println("Test case: " + i + " should be: " + correctResults.get(i) + " but was: " + results.get(i));
System.out.println("Test case: " + i + " input array: " + Arrays.toString(testInputs.get(i)));
}
}
}
Кроме того, если вам все равно, уничтожается ли определенное значение, вы можете избежать дополнительной переменной:
private static boolean checkIfRemovingMaxOneElementItIsStrictlyIncreasing_WithoutAssignment(final int[] sequence)
{
boolean isFirstNonDecreasingSequence = true;
final int length = sequence.length;
for (int i = 1; i < length; i++)
{
if (sequence[i] <= sequence[i - 1])
{
if (isFirstNonDecreasingSequence == true)
{
if ((i + 1) < length) // check this is not the last element
{
if ((sequence[i - 1] >= sequence[i + 1])) // Check if it is peak or pit
{
// [i-1] is a local peak. Remove [i-1]
if (i > 1)
{
// Check if by removing [i-1] the sequence is actually increasing
if (sequence[i] <= sequence[i - 2])
{
return false;
}
}
}
else
{
// [i] is a local pit. Remove [i]
sequence[i] = sequence[i - 1];
}
isFirstNonDecreasingSequence = false;
}
}
else
{
return false;
}
}
}
return true;
}
В обеих версиях много кода внутри кода. Это правда, но они будут выполнены только в первый раз, когда последовательность обнаружит не увеличивающуюся последовательность двух последовательных значений. Так что с точки зрения производительности это должно быть хорошо.
Что касается логики:
Когда он обнаруживает, что по индексу [i]: A[i-1]>=A[i], он определяет, находится ли его после пика (таким образом, A [i-1] является "ненормально" высоким и должен быть удален из последовательность) или он находится внутри ямы (A [i] слишком низок и должен быть удален из последовательности).
Ваш код содержит 2 вложенных for циклы, которые оба перебирают весь список. Это означает, что если ваш список содержит 100000 элементов, в худшем случае для кода потребуется 100000*100000 шагов. Конечно, это медленно.
Поскольку список всегда "почти отсортирован", вам, вероятно, не нужно проверять начало списка, поскольку вы уже знаете, что он отсортирован. Интуитивно должно быть достаточно взглянуть на последние несколько элементов списка и запомнить, сколько несортированных пар содержится в списке.
Обновлено 2: попробуйте этот код также (в макс. 2 циклах) Дальнейшая оптимизация возможна, но все равно дает время O(n)
public class TstList {
public static boolean compute(int a[]) {
if (compute_1(a))
return true;
return compute_2(a);
}
public static boolean compute_1(int a[]) {
if (a.length < 2)
return true;
int previous = a[0];
int counter = 0;
for (int i = 1; i < a.length; i++) {
if (previous < a[i]) {
previous = a[i];
continue;
} else {
if (i == 1)
previous = a[i];
else
previous = a[i - 1];
counter++;
}
if (counter > 1)
return false;
}
return true;
}
public static boolean compute_2(int a[]) {
if (a.length < 2)
return true;
int previous = a[0];
int counter = 0;
for (int i = 1; i < a.length; i++) {
if (previous < a[i]) {
previous = a[i];
continue;
} else {
previous = a[i];
counter++;
}
if (counter > 1)
return false;
}
return true;
}
public static void main(String arg[]) {
System.out.println(compute(new int[] { 1, 2, 3, 4, 6 })); \\1
System.out.println(compute(new int[] { 1, 2, 3, 1, 4, 6 })); \\2
System.out.println(compute(new int[] { 1, 2, 1, 3, 1, 4, 6 })); \\3
System.out.println(compute(new int[] { 1, 2, 3, 4, 6, 3 })); \\4
System.out.println(compute(new int[] { 3, 2, 1 })); \\5
System.out.println(compute(new int[] { 10, 1, 2, 3, 4, 5 })); \\6
System.out.println(compute(new int[] { 1, 2, 5, 3, 5 })); \\7
}
}
выход
true \\1
true \\2
false \\3
true \\4
false \\5
true \\6
true \\7