LeetCode——oj练习之原地删除数值中的元素
我们来看这道题思路有如下:
1.利用循环判断数组的某个元素是否为需要移除的元素,如果是的话那么就将后面的元素先前覆盖一格,直到循环结束。
相关代码如下
时间复杂度为O(n^2)
int removeElement(int* nums, int numsSize, int val) { for(int i=0;i<numsSize;i++) { if(nums[i]==val) { for(int j=i;j<numsSize;j++) { nums[j]=nums[j+1]; } numsSize--; } } }
2.创建一个新数组,遍历原数组,如果原数组的元素不是需要移除的那个,就把该元素放到那个新数组中,如果是需要移除的那个就跳过;
int removeElement(int* nums, int numsSize, int val) { int src=0;,dest=0; int arr[10]={0}; while(src<numsSize) { if(nums[src] != val) { arr[dest]=nums[src]; src++;dest++; } else { src++; } } }
3.最优解法:让数组上下同时进行遍历,如果此时的元素不是要删除的元素,那么用自己去覆盖自己,否则向前跳;
int removeElement(int* nums, int numsSize, int val){ int src=0;int dest=0; while(src<numsSize) { if(nums[src]==val) { src++; } else { nums[dest]=nums[src]; src++; dest++; } } return dest; }
这个思路无论是从时间复杂度还是空间复杂度来说都是最优解
下一篇:
【数据结构】双向链表