设计算法，在数组r[n]中删除所有元素值为x的元素，要求时间复杂度为O(n)，空间复杂度为O(1)。

野性酷女 2021-07-24 15:02 577阅读 0赞

## 设计算法，在数组r\[n\]中删除所有元素值为x的元素，要求时间复杂度为O(n)，空间复杂度为O(1)。 ##

## 1、思路 ##

我们遍历整个原数组，当原数组的值等于`x`时,我们跳过不进行处理，否则我们将该值记录到新的数组中。这样我们遍历整个数组的时间复杂度是 O ( n ) O(n) O(n),而删除指定元素的时间复杂度为 O ( 1 ) O(1) O(1)。除去原数组和新数组的空间复杂度为 O ( n ) O(n) O(n),在此过程中，指定元素`x`的空间复杂度为 O ( 1 ) O(1) O(1)。

**核心代码：**

int k = 0; 
    	for(int i = 0; i < n; i++) 
    	{ 
    		if(a[i] == x)  continue;
    		else 
    		{ 
    			b[k++] = a[i];
    		}
    	}

## 2、测试数据 ##

第一行输入`n`,`x`,分别代表原数组的长度和要删除元素的值，第二行输入原数组的值。

输出在原数组中删除所有元素值为`x`的元素后的数组。

**输入：**

10 2
    2 3 4 5 6 7 2 2 9 13

**输出：**

3 4 5 6 7 9 13

**输入：**

7 5
    4 5 5 6 8 9 5

**输出：**

4 6 8 9

## 3、完整代码 ##

#include<stdio.h>
    const int N = 10010;
    int a[N]; //原数组
    int b[N]; //记录删除指定元素后的数组 
    int main()
    { 
        int n,x;
    	scanf("%d%d",&n,&x);  //输入数组长度和要删除元素的值 
    	for(int i = 0 ; i < n; i++) scanf("%d",&a[i]);
    	int k = 0; 
    	for(int i = 0; i < n; i++) 
    	{ 
    		if(a[i] == x)  continue;
    		else 
    		{ 
    			b[k++] = a[i];
    		}
    	} 
    	for(int i = 0; i < k; i++ )  printf("%d ",b[i]);
    	return 0;
    }