java – 以时间效率方式将大数组中的所有零值移动到其前部

发布时间：2020-12-15 05:16:32 所属栏目：Java 来源：网络整理

导读：您将获得一个具有Integral类型值的大数组,如何以时间效率方式将其中的所有零值移动到数组的前部？例如0,1,72,3,5,9,6,51,3 — 0,3 问候！解决方法如果要保持其他项之间的顺序,请向后循环复制所有非零项,然后在开头填写零项： int source = arr.Length - 1

您将获得一个具有Integral类型值的大数组,如何以时间效率方式将其中的所有零值移动到数组的前部？

例如0,1,72,3,5,9,6,51,3 —> 0,3

问候！

解决方法

如果要保持其他项之间的顺序,请向后循环复制所有非零项,然后在开头填写零项：

int source = arr.Length - 1;
int dest = arr.Length - 1;
while (source >= 0) {
  if (arr[source] != 0) {
    arr[dest--] = arr[source];
  }
  source--;
}
while (dest >= 0) arr[dest--] = 0;

如果项目的顺序不重要,您可以简单地将零项目与数组开头的项目交换：

int dest = 0;
for (int source = 0; source < arr.Length; source++) {
  if (arr[source] == 0) {
    arr[source] = arr[dest];
    arr[dest++] = 0;
  }
}

两种算法都是O(n).

(C#中的例子,但它应该足够接近,因为它主要是关于算法的问题……)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!