首页 > 代码库 > LeetCode:Remove Element
LeetCode:Remove Element
题目链接
Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn‘t matter what you leave beyond the new length.
题目的意思是把数组中和给定的目标数字不同的元素,全部放到数组的前部
遍历数组,如果在当前位置 i 碰到元素等于给定的目标数字,从数组尾部找一个不等于目标的数字,放到 i 位置
class Solution {public: int removeElement(int A[], int n, int elem) { int k = n-1; for(int i = 0; i <= k; i++) if(A[i] == elem) { while(k > i && A[k] == elem)k--;//从后面找到第一个不是elem的元素 if(k == i)return i; else A[i] = A[k--];//k位置非elem的元素放到i位置 } return k+1; }};
其实遍历找到等于目标数字的元素后,只需要把数组尾部元素放到当前位置,不管尾部元素是否为目标数字 本文地址
class Solution {public: int removeElement(int A[], int n, int elem) { int k = n-1; for(int i = 0; i <= k;) if(A[i] == elem) A[i] = A[k--];//尾部元素放在当前位置 else i++; return k+1; }};
还有一种思路是把不等于目标数字的元素依次放到首部,如果不等于目标数字的元素较少,这种方法效率更高
class Solution {public: int removeElement(int A[], int n, int elem) { int k = 0; for(int i = 0; i < n; i++) if(A[i] != elem)A[k++] = A[i]; return k; }};
【版权声明】张转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3793601.html
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。