Пытаюсь реализовать оптимизацию наивного алгоритма, в соответствии с подсказкой https://acmp.ru/article.asp?id_text=198
До этой "оптимизации" все компилировалось, но не проходило валидацию по времени. Сейчас же при компиляции выдает очевидно неверные результаты. Помогите плиз разобраться😳
package com.javarush.task.task20.task2025;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/*
Алгоритмы-числа
*/
public class Solution {
public static long[] getNumbers(long N) {
long exponentiation; //возведенная в требуемую степень цифра числа
long finalExp = 0; //сумма всех exponentiation для каждого числа
ArrayList<Long> effectiveNumbers = new ArrayList<>(); //выведенные эффективные числа
ArrayList<Long> partsOfNumbers = new ArrayList<>(); //разделение эфф.чисел на цифры для сравнения
/* Алгоритм для упрощения вычисления чисел Армстронга: если любая цифра не меньше предыдущей и
не больше последующей - add в effectiveNumbers, работаем только с ними.
Например: 12, 1557, 333 и т.д. https://acmp.ru/article.asp?id_text=198 */
for (long j = N - 1; j > 0; j--) { //для каждого числа j от N - 1 до 0
while (j != 0) {
partsOfNumbers.add(0, j % 10);
j /= 10;
} // в цикле получаем список из цифр числа
for (int i = 0; i < partsOfNumbers.size() - 2; i++) {
if (partsOfNumbers.get(i) <= partsOfNumbers.get(i + 1) &&
partsOfNumbers.get(i + 1) <= partsOfNumbers.get(i + 2)) {
effectiveNumbers.add(Long.parseLong(partsOfNumbers.get(i) + ""
+ partsOfNumbers.get(i + 1) + "" + partsOfNumbers.get(i + 2)));
} /*если любая цифра не меньше предыдущей и
не больше последующей - add в effectiveNumbers*/
}
partsOfNumbers.clear();
}
/*Далее для каждого числа из списка эффективных чисел выполняем наивный алгоритм возведения
в степень, и сравниваем с каждым числом меньше N. Если совпадают - добавляем в финальный список.*/
String effectNumber; //каждое число из эффективного списка
String everyDigit; //каждая цифра этого числа
ArrayList<Long> list = new ArrayList<>(); //список для полученных чисел
for (long l : effectiveNumbers) { //для каждого из отобранных чисел
effectNumber = l + "";
for (int g = 0; g < effectNumber.length() - 1; g++) {
everyDigit = effectNumber.charAt(g) + ""; //каждая цифра числа N
exponentiation = (long) Math.pow(Integer.parseInt(everyDigit), effectNumber.length());
//возводим цифру в нужную степень
finalExp += exponentiation; //сумма всех степеней цифр числа
}
for (long everyNumbLowerN = N - 1; everyNumbLowerN > 0; everyNumbLowerN--) {
if (everyNumbLowerN == finalExp)
list.add(everyNumbLowerN);
/*Сравниваем с каждым числом меньше N.
Если совпадают - добавляем в финальный список*/
}
finalExp = 0;
}
Collections.sort(list);
long[] result = new long[list.size()]; //заполняем массив списком полученных чисел
for (int k = 0; k < list.size(); k++) {
result[k] = list.get(k);
}
return result;
}
public static void main(String[] args) {
long a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(1000)));
long b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(1000000)));
b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
}
}