algorithm - 在小于O（n）的范围内覆盖arraylist(coverting arraylist to array in less than O(n))

Question

I am currently working on program and want to convert ArrayList to an array but in less than O(n) time.

(我目前正在研究程序，想将ArrayList转换为数组，但少于O（n）的时间。)

  for (int i = 0; i < list.size(); i++) {




    if (list.get(i) != null) {
                                 arr[i] = list.get(i);
                             }
                     }

  ask by DESI RECORDS translate from so

Answer 1

If n is the length of the list then O(n) means in this case that you look at each element in the list and copy it.

(如果n是列表的长度，则O（n）在这种情况下意味着您查看列表中的每个元素并将其复制。)
Now you say you want to convert it in less than O(n).

(现在，您说要转换为小于O（n）的值。)

This means you have to ignore some elements in the list.

(这意味着您必须忽略列表中的某些元素。)

if not it would be O(n) again.

(如果不是，它将再次为O（n）。)

But which do you ignore?

(但是您忽略了哪些？)

Remember you are not allowed to look at all elements else it would be in O(n) again.

(请记住，不允许您再查看所有其他元素，否则它将再次出现在O（n）中。)
Let's say you know that the list contains booleans where n/2 are true and the others are false.

(假设您知道列表包含布尔值，其中n / 2为true，其他为false。)

In the best-case scenario all true values would be in the first half of the list.

(在最佳情况下，所有真实值都在列表的前半部分。)

Now you can stop iterating at n/2 of the list but you need to add the false values again to your Array.

(现在您可以在列表的n / 2处停止迭代，但是您需要再次将false值添加到Array中。)

Now you are in O(n) again.

(现在您又在O（n）中。)
Let's make another assumption.

(让我们做另一个假设。)

You can always ignore the last value of the list.

(您始终可以忽略列表的最后一个值。)

This means that you only iterate n-1 times that then is O(n-1) but in big O notation, you ignore constants so it gets O(n) again.

(这意味着您仅迭代n-1次，然后是O（n-1），但是使用大O表示法时，您将忽略常量，因此它将再次获得O（n）。)

It is not possible to copy all n elements of a list to an Array in lower than O(n).

(不可能将列表的所有n个元素都复制到O（n）以下的Array中。)