27. Remove Element - 移除元素-Easy
Description:
Given an array and a value, remove all instances of that value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example:
Given input array nums = [3,2,2,3]
, val = 3
Your function should return length = 2, with the first two elements of nums being 2.
思路分析:
1.最终要求的是输出除给定值以外的其他数组中的值,所写方法需要返回的是这些值的总个数,即输入[3,2,2,3]==>输出:2,并且数组的新状态为[2,2,3,3];
2.最近在复习排序算法,所以这个问题很亲切,其中也一种排序的影子,只不过是把特定的值而不是最大值放到最后,问题还有一个约束:只能用常数级的额外空间,即O(n)=1,所以不能通过额外的数组来记录给定值以外的值完成;
3.因此,排序里面每一次循环里怎么把局部最大值移动到局部的最后,这里也可沿用,只不过,这里问题有其特殊性:值一旦已经确定了,不需要后续的一轮比较来确定(排序的时候最大值需要这样来确定),一旦遍历到就可以直接当做‘最大值’来移动到最左边,而且最大值只有一个,但特定值可以同时出现。
C#代码:
public class Solution {
public int RemoveElement(int[] nums, int val) {
int j=nums.Length-,len= nums.Length,i=;
while(j>=i){
if(nums[j]==val){
len--;
j--;
continue;
}
if(nums[i]==val){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
len--;
j--;
}else{
i++;
}
if(i==j){
break;
}
}
return len;
}
}
或者:
public class Solution {
public int RemoveElement(int[] nums, int val) {
int len= nums.Length;
for(int i=;i<nums.Length;i++){
if(i==len)break;
if(nums[i]==val){
if(nums[len-]==val){
len--;
i--;
continue;
}
int temp = nums[i];
nums[i] = nums[len-];
nums[len-] = temp;
len--;
}
}
return len;
}
}
最新文章
- git命令分类图
- cocoapods使用一直Updating local specs repositories的解决方案
- RCurl网络数据抓取
- Plextor 浦科特M7VC性能
- JAVA 接口与抽象类的区别
- Java基础之序列化对象——反序列化对象(DeserializeObjects)
- 一些qml资料
- 【avalon】data
- 错误 1 无法嵌入互操作类型“Microsoft.Office.Interop.Excel.ApplicationClass”。请改用适用的接口
- C# 实现无焦点窗体(转载)
- 国内开源html5游戏引擎全收录
- 【剑指offer】面试题31:连续子数组的最大和
- Android进阶练习一
- 宣布在 Azure 镜像库中正式推出 Windows Server 2012 R2 并降低 Windows Azure 的实例定价
- Linux与JVM的内存关系分析(转)
- 《Intel汇编第5版》 汇编拷贝字符串
- Javascript隔离方法
- select应用于read函数 超时非阻塞方式
- php中常用的字符串长度函数strlen()与mb_strlen()实例解释
- 对Java中多态,封装,继承的认识(重要)