Строковый массив в Java

Question

Можно ли получить ответ в псевдокоде, ребята?

Как мне написать метод, который в O (n log n) берет строковый массив и удаляет пустые записи.

Я ценю, что вы не можете изменить размер массива, что означает, что мне нужно скопировать содержимое в новое, но я могу только сделать это с помощью вложенных циклов for, которые сжимают время моего алгоритма и затем становятся O п ^ 2)

Answer 1

Вам нужно сделать копию массива, но вам нужно сделать только поверхностную копию, а не глубокую копию - отдельные строки копировать не нужно. Так это будет выглядеть примерно так:

create new output array O
for each string S in the input array I
    if S is not null
        add S to O

Если вы используете ArrayList s, вы можете использовать это как есть; однако, если вы используете простые старые массивы Java, вы не можете изменять его размер каждый раз, когда добавляете элемент. Таким образом, вместо этого вам нужно сначала подсчитать количество ненулевых записей, затем создать выходной массив соответствующего размера, а затем снова просмотреть цикл ввода.

Answer 2

Ваш вопрос предполагает, что вы, возможно, искали способ избежать выделения нового массива. Если это так, это решение может быть тем, что вы ищете. Вместо того, чтобы возвращать массив меньшего размера, он вместо этого модифицирует данный массив, перемещая все нулевые ссылки в конец и упаковывая все строки впереди. Так, например, {"Foo","Bar",null,"Baz"} становится {"Foo","Bar","Baz",null}.

public static void packStrings(String[] strArr) {
    int writeIndex = 0;
    for (String str : strArr)
        if (str != null) strArr[writeIndex++] = str;
    Arrays.fill(strArr, writeIndex, strArr.length, null);
}

И в псевдокоде это было бы ... ах ...

function packString(stringArray)
    initialize write index to 0
    for each string in stringArray
        if the string isn't null
            write it to stringArray at the write index
            advance the write index
    set the rest of stringArray at the write index and beyond to null

Это O (n), но, более того, это просто n массивов и нулевых распределений.

Answer 3

Вы должны следить за своим прогрессом через оба массива. Пусть a [] будет исходным массивом, а b [] будет вторым массивом того же размера.

 initialize acount to 0
 initialize bcount = 0
 for acount = 0 to a.length - 1
   if(array[acount] != null)
      b[bcount++] = a[acount]

  return b[]

В конце b будет содержать только bcount + 1 записей, которые меньше или равны длине массива. Поэтому, по желанию, вы можете определить массив только с элементами bcount для возврата.