Удаление отрицательных чисел из массива в Java

Ответ 1

Как улучшить сложность кода или есть хороший алгоритм?

Вот линейный алгоритм O(n) с постоянным пространством (пренебрегая пространством, необходимым для выходного массива). Когда элемент неотрицателен, скопируйте элемент и продвигайте как выходной массив, так и входной массив. И когда элемент отрицательный, продвигайте только входной искатель массива (indx) и избегайте копирования в выходной массив.

public static int[] removeNegativeNumbers(int[] num) {
    int[] output = new int[num.length];
    int k = 0;
    for(int i = 0; i < num.length; i++) {
       if(num[i] >= 0) {
           output[k++] = num[i];
       }
    }
    return Arrays.copyOfRange(output, 0, k);
}

Пространственное эффективное решение

Вы можете сделать алгоритм на месте, преобразовывая входной массив для хранения вывода, как способ сортировки вставки, чтобы избежать служебных затрат пространства выходного массива.

public static int removeNegativeNumbers(int[] num) {
    int k = 0;
    for(int i = 0; i < num.length; i++) {
       if(num[i] >= 0) {
           num[k++] = num[i];
       }
    }
    // Now input array is holding the output data
    // Return the length of output array
    return k;
}

// Usage: int newLen = removeNegativeNumbers(array);

Это называется метод двух указателей, очень простой, но полезный для решения многих классических головоломок, таких как дедупликация Array, объединение двух отсортированных массивов, пересечение двух отсортированных массивов и т.д.

Ответ 2

Как насчет потоков Java 8?

Arrays.stream(num).filter(s -> s >= 0).toArray();

Ответ 3

Я не думаю, что мы сможем улучшить ситуацию с точки зрения эффективности, чем @kaidul-islam answer (и @user6904265 с точки зрения лаконичности).

Я просто добавляю решение, которое должно иметь некоторую ценность в очень специфическом сценарии, где негативы редко появляются, а массив очень большой.

Основная идея состоит в том, чтобы отложить фактическую копию до тех пор, пока не будет найдено отрицательное значение, а затем скопируйте ее с помощью System.arraycopy. Если отрицательный результат не найден, будет возвращен исходный массив.

import java.util.*;

public class NotNegativeTest {

    public static void main(String[] args) {
         int[] array = { 1, -3, 4, -9, 3, 4, 70, -10, 0, 7 }; 
         System.out.println(Arrays.toString(removeNegativeNumbers(array))); 
    } 

    public static int[] removeNegativeNumbers(int[] num) {
         int[] output = new int[num.length];
         int k = 0;
         int i = 0; 
         int last=-1;
         int howmany=0;

         while(i < num.length) {
             if(num[i] < 0) {
                howmany=i-last-1;
                switch(howmany) {
                    case 0: break;
                    case 1: 
                            output[k]=num[last+1];
                            k++;
                            break;
                    default:        
                            System.arraycopy(num, last+1,  output, k, howmany);
                            k+=howmany;
                }
                last=i;
             } 
             i++;
         } 
         if (last>=0) {
              if(last!=i-1) {
                howmany=i-last-1;  
                System.arraycopy(num, last+1,  output, k, howmany);
                k+=howmany;
            }
        } else {
            return num;
        }

         return Arrays.copyOfRange(output, 0, k);
     }

}

Я нашел время написать микропредметку JMH.

Я использовал эти конфигурации:

Options opts = new OptionsBuilder()
  .include(MyBenchmark.class.getSimpleName())
  .mode(Mode.AverageTime)
  .warmupIterations(1)
  .warmupTime(TimeValue.seconds(5))
  .measurementIterations(10)
  .measurementTime(TimeValue.seconds(5))
  .jvmArgs("-server")
  .forks(1)
  .build();
new Runner(opts).run();

(отказ от ответственности: мой первый тест JMH, поэтому, если у кого-то есть предложения, я буду рад изменить его и обновить результаты)

И вот результаты:

# Run complete. Total time: 00:02:54

Benchmark                             Mode  Cnt  Score   Error  Units
MyBenchmark.testMethodUser6904265     avgt   10  0,201 ± 0,040   s/op
MyBenchmark.testMethodInsac           avgt   10  0,093 ± 0,022   s/op
MyBenchmark.testMethodKaidul          avgt   10  0,124 ± 0,029   s/op

Теперь, прежде чем подбадривать меня, пожалуйста, взгляните на то, насколько предвзятым был тест:

 int[] array = new int[10000000];
 array[0]=-5;
 array[10000]=-3;
 array[40000]=-3;
 array[8000000]=-3;

 int[] answer=NotNegativeTest.removeNegativeNumbers(array);

Итак, обратите внимание, что это не то, что мой метод выиграл (тест был написан для моего метода, чтобы выиграть:-), но насколько близким был общий метод кайдул-ислама даже в этом экстремальном сценарии.

ОБНОВЛЕНО: вот ссылка на jmh benchmark, который я написал, чтобы вы могли проверить более реалистичный сценарий (если кто-то обнаружит проблемы с тем, как я настройте тест, пожалуйста, дайте мне знать). Существует зависимость от Trove для теста, который я сделал с другим ответом.

Ответ 4

Это будет сделано с единственной итерацией:

Удерживайте 2 индекса: src и dst в исходном массиве. оба инициализируются на 0.

когда число положительное, скопируйте его с num[src] на num[dst] и продвигайте оба индекса

когда число отрицательное, просто перейдите src.

возвращает исходный массив с dst в качестве его нового размера.

public static int removeNegativeNumbers(int[] num) {
  int dst=0;
  for (int src=0 ; src<num.length ; ++src)
    if (num[src]>=0)
      num[dst++] = num[src];
  return dst;
}

Ответ 5

Поскольку вам обязательно нужно посмотреть на каждый отдельный элемент, чтобы определить, меньше ли он, время выполнения должно быть не менее O (n). Так как пространство, необходимое для хранения ввода, равно O (n), пространство не менее O (n). Ваше решение работает в O (n) времени с сложностью O (n), поэтому никакое решение не может иметь более сложное пространство или сложность выполнения, чем ваше решение

Однако мы можем получить лучшие результаты, если предположить, что массив отсортирован. Затем мы выполняем двоичный поиск 0. Если у нас есть способ вернуть субмассив с постоянным временем (например, магию указателя в C или просто вернуть начальный индекс для чтения), тогда алгоритм будет иметь O ( log n).

Ответ 6

Следуйте приведенному ниже коде (Java 8)

int test[] = new int[] { 15, -40, -35, 45, -15 };
    // here we can take the test array in to stream and filter with condition (>=0).
    int[] positives = Arrays.stream(test).filter(x -> x >= 0).toArray();

    System.out.println("Here is the positive array elements");

    for (int i : positives) {
        System.out.print(i + "\t");
    }

Ответ 7

public static int[] removeNegativeNumbers(int[] num) {
    List<Integer> list = new ArrayList<>();
    for (int n : num) {
        if (n >= 0) {
            list.add(n);
        }
    }
    return list.toArray(new int[list.size()]);
}