Как улучшить эффективность
Напишите функцию:
class Solution{
public int solution(int[] A);
}
что, учитывая массив A из N целых чисел, возвращает наименьшее положительное целое число (больше 0), которого нет в A.
Например, если A = [1,3,6,4,1,2], функция должна вернуть 5.
Учитывая A = [1,2,3], функция должна вернуть 4.
Учитывая A = [-1, -3], функция должна вернуть 1.
Напишите эффективный алгоритм для следующих предположений.
N представляет собой целое число в диапазоне [1..100,000];
каждый элемент массива A является целым числом в диапазоне [-1,000,000..1,000,000].
Я написал следующий алгоритм на Java:
public class TestCodility {
public static void main(String args[]){
int a[] = {1,3,6,4,1,2};
//int a[] = {1,2,3};
//int b[] = {-1,-3};
int element = 0;
//checks if the array "a" was traversed until the last position
int countArrayLenght = 0;
loopExtern:
for(int i = 0; i < 1_000_000; i++){
element = i + 1;
countArrayLenght = 0;
loopIntern:
for(int j = 0; j < a.length; j++){
if(element == a[j]){
break loopIntern;
}
countArrayLenght++;
}
if(countArrayLenght == a.length && element > 0){
System.out.println("Smallest possible " + element);
break loopExtern;
}
}
}
}
Это делает работу, но я уверен, что это не эффективно. Поэтому мой вопрос: как улучшить этот алгоритм, чтобы он стал эффективным?
4 ответа
Основная идея такая же, как у Дениса. Сначала сортируйте, затем обрабатывайте, но используя функцию java8. Есть несколько методов, которые могут увеличить время. (Не очень уверен, насколько эффективен java 8 обрабатывает их: фильтруйте, различайте и даже занимайте время... в худшем случае у вас есть что-то похожее с 3 полными циклами. Один дополнительный цикл предназначен для преобразование массива в поток). В целом вы должны получить ту же сложность во время выполнения.
Одним из преимуществ может быть многословие, но также необходимы некоторые дополнительные знания по сравнению с решением Дениса.
import java.util.function.Supplier;
import java.util.stream.IntStream;
public class AMin
{
public static void main(String args[])
{
int a[] = {-2,-3,1,2,3,-7,5,6};
int[] i = {1} ;
// get next integer starting from 1
Supplier<Integer> supplier = () -> i[0]++;
//1. transform array into specialized int-stream
//2. keep only positive numbers : filter
//3. keep no duplicates : distinct
//4. sort by natural order (ascending)
//5. get the maximum stream based on criteria(predicate) : longest consecutive numbers starting from 1
//6. get the number of elements from the longest "sub-stream" : count
long count = IntStream.of(a).filter(t->t>0).distinct().sorted().takeWhile(t->t== supplier.get()).count();
count = (count==0) ? 1 : ++count;
//print 4
System.out.println(count);
}
}
Существует много решений со сложностью O(n) и типа O(n). Вы можете конвертировать массив в;
- set: массив для установки и проверки цикла (1...N) содержит число или нет. Если не вернуть номер.
- hashmap: массив для отображения и проверки цикла (1...N) содержит число или нет. Если не вернуть номер.
- Массив count: преобразовать данный массив в массив счетчиков положительного массива, например, если arr[i] == 5, countArr[5]++, если arr[i] == 1, countArr[1]++, затем проверьте каждый элемент в countArr с помощью для цикла (1...N) независимо от того, будет ли он больше 1 или нет. Если не вернуть его.
На данный момент выглядит более эффективный алгоритм, как упомянутое @Ricola. Решение Java с O(n) сложностью времени и O(1) пространственной сложностью:
static void swap(final int arr[], final int i,final int j){
final int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static boolean isIndexInSafeArea(final int arr[], final int i){
return arr[i] > 0 && arr[i] - 1 < arr.length && arr[i] != i + 1 ;
}
static int solution(final int arr[]){
for (int i = 0; i < arr.length; i++) {
while (isIndexInSafeArea(arr,i) && arr[i] != arr[arr[i] - 1]) {
swap(arr, i, arr[i] - 1);
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] != i + 1) {
return i+1;
}
}
return arr.length + 1;
}
Вы должны понять Big O и сложности во время выполнения. Это универсальная конструкция для лучшего понимания эффективности в коде.
Проверьте этот веб-сайт, он показывает график сложности во время выполнения с точки зрения Big O, который может помочь вам в поиске более эффективного программирования.
Однако, короткая история... Наименьшее количество операций и памяти, потребляемых произвольной программой, является наиболее эффективным способом достижения того, что вы намеревались сделать с вашим кодом.
Вы можете сделать что-то более эффективное, уменьшив избыточность в своих алгоритмах и избавившись от любой операции, которая не должна выполняться для достижения того, что вы пытаетесь сделать
Дело в том, чтобы отсортировать ваш массив, а затем итерировать по нему. С отсортированным массивом вы можете просто пропустить все отрицательные числа, а затем найти минимальный возможный элемент, который вам нужен.
Вот более общее решение для вашей задачи:
import java.util.Arrays;
public class Main {
public static int solution(int[] A) {
int result = 1;
Arrays.sort(A);
for(int a: A) {
if(a > 0) {
if(result == a) {
result++;
} else if (result < a){
return result;
}
}
}
return result;
}
public static void main(String args[]){
int a[] = {1,3,6,4,1,2};
int b[] = {1,2,3};
int c[] = {-1,-3};
System.out.println("a) Smallest possible " + solution(a)); //prints 5
System.out.println("b) Smallest possible " + solution(b)); //prints 4
System.out.println("c) Smallest possible " + solution(c)); //prints 1
}
}
Сложность этого алгоритма должна быть O(n*log(n))