String array in Java

Would it be possible to get an answer in pseudocode please, guys?

Ho开发者_运维知识库w could I write a method that, in O(n log n), takes a string array and removes null entries.

I appreciate you can't alter the array size which means I need to copy the contents over to a new one but I can only seem to do it with nested for-loops which compresses my algorithm time and would then become O(n^2)

---

You need to make a copy of the array, but you only need to make a shallow copy, not a deep copy -- the individual strings don't need to be copied. So it would look something like this:

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

If you're using ArrayLists, you can use this as-is; however, if you're using plain old Java arrays, you can't resize it each time you add an element. So, instead, you'll need to count the number of non-null entries first, then create an output array of the appropriate size, then loop through the input array again.

---

Your question suggests that you might be looking for a way to avoid allocating a new array. If that's the case, this solution might be what you're looking for. Rather than returning an array of a smaller size, it instead modifies the given array, moving all null references to the end and packing all the Strings at the front. So {"Foo","Bar",null,"Baz"} becomes {"Foo","Bar","Baz",null}, as an example.

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);
}

And in psudocode that would be... ah....

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

That's O(n), but more so, that's a mere n array assignments and zero allocations.

---

You need to keep track of your progress through both arrays. Let a[] be the original array and b[] be a second array of the same size.

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

  return b[]

At the end b will contain only bcount + 1 entries which is less than or equal to the length of the array. So optionally you may want to define an array with only bcount elements to return.