我遇到了一个hackerrath编码问题,在这个问题中,您必须在整数数组上执行以下任务-
在数组中搜索特定的数字并用1替换它的出现次数
将所有1移动到数组的第一部分,保持数组的原始顺序
例如-如果我们有一个整数数组 {22,1,34,22,16,22,35,1}
,这里我们搜索数字“22”(假设它存在于数组中),将其替换为1,并将所有这些1(包括已经存在的1)移动到数组的第一部分,得到的数组应该如下所示 {1,1,1,1,1,1,34,16,35}
-保持数组的原始顺序,最好使用java。实际上,我已经编写了一个解决方案,它工作正常,但不是最优的,有人能帮我找到一个最优的解决方案(w.r.t.时空复杂性)?
下面是我的解决方案-
public static void main(String[] args) {
int[] n = rearr(new int[] {22,1,34,22,16,22,1,34,1}, 22);
for(int i=0; i<n.length; i++) {
System.out.print(n[i]+" ");
}
}
static int[] rearr(int[] a, int x) {
int[] temp = new int[a.length];
int j=0, c=0, k=0;
//search and replace
for(int i=0; i<a.length; i++) {
if(a[i] == x) {
a[i] = 1;
}
}
//shift all 1s to first part of array or shift all non-1s to last part of the array
for(int i=0; i<a.length; i++) {
if(a[i] != 1) {
temp[j] = a[i];
j++;
}
if(a[i] == 1) {
c++;
}
}
j=0;
for(int i=0; i<a.length && c>0; i++, c--) {
a[i] = 1;
j++;
}
for(int i=j ;i<a.length; i++) {
a[i] = temp[k];
k++;
}
return a;
}
2条答案
按热度按时间gpfsuwkq1#
这可以在通过数组的单个迭代中完成。我们可以在这里使用2指针方法,在这里我们将使用一个指针遍历数组,另一个指针指向数组中1的索引。
代码如下:
这里我们初始化j=-1,因为我们认为数组中不存在1。然后我们开始从数组的末尾到数组的开头迭代数组,因为我们必须将所有的1推到数组的开头。现在当我们到达1或x(在你的例子中是特定的数字)时,我们检查这是否是x或1的第一次出现,如果是,那么我们用这个索引初始化j,并且改变arr[i]=1,因为这可能等于x,那么我们需要使它为1。如果arr[i]不是1或x,这意味着它是一个我们需要在数组后面推的数字。我们检查位置是1还是j=-1。如果j=-1,这意味着这个数字已经在数组末尾被向后推,否则我们交换i和j处的数字,并将j减1。
在数组的末尾,我们将按照所需的方式对数组进行排序。
时间复杂度:由于我们只迭代数组1,因此时间复杂度为o(n)。空间复杂度:由于没有额外的空间被使用,也没有常量空间被使用,因此空间复杂度为o(1)
p1tboqfb2#
这可以在线性时间和空间复杂度下完成,方法是返回一个全新的列表,而不是修改原始列表。
这是线性空间复杂性,因为它需要与给定列表大小相等的额外空间。它是线性时间复杂度,因为在最坏的情况下,它会在列表大小上迭代两次。
作为奖励,如果我们决定离开原来的
1
如果他们在那里,我们可以做到这一点没有任何麻烦,通过简单地修改if
条件。如果我们决定要将填充值更改为其他值,也是一样的。在空间复杂度不变的情况下执行此操作需要
O(n^2)
列出复杂性,因为它需要在a
到他们适当的位置。最简单的方法可能是在第一次遍历列表时进行替换,然后执行类似于bubblesort的操作来移动所有列表1
他在前面。