删除排序数组中的重复项
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
这其实是我以前做过的一道题,但是昨天无聊去翻的时候发现解答很繁琐,解答如下
public int removeDuplicates(int[] nums) {
int count = nums.length;
int length = count;
int i=0;
if (count>1){
while (i<length-1){
if (nums[i]>nums[i+1]){
break;
}
if (nums[i]==nums[i+1]){
length--;
int temp = nums[i];
count--;
for (int j=i;j<nums.length-1;j++){
nums[j] = nums[j+1];
}
nums[nums.length-1] = temp;
i=0;
continue;
}
i++;
}
if(count==2){
if (nums[0]==nums[1]){
return 1;
}
}
}
return count;
}
说实话,我都不知道我是怎么做出来的,而且还通过了…估计有打表嫌疑,所以我又重新做了一遍,这一次相比而言就要清晰明了很多了
public int removeDuplicates(int[] nums) {
int pos = 0;
for(int i=1;i<nums.length;i++){
if(nums[pos]!=nums[i]){
nums[++pos] = nums[i];
}
}
return ++pos;
}
逻辑其实很简单
- 如果相邻两个数相同的话就不操作
- 如果相邻两个数不相同的话则将进行比较的右边的数放到左边数的旁边(有点绕,我举个例子)
示例数组[1,1,2],使用如上代码逻辑(简单的那个)
- 比较[1,1],由于两个数相同,不进行操作,此时nums[0]=1,nums[1]=1
- 然后i++,nums[0]=1,nums[2]=2,两个数不同,那么执行nums[++pos] = nums[i],相当于就是nums[1]=nums[2],以此类推
总结:
- 数组是引用类型传递。
- 优化代码的感觉真爽。
下一篇: 在一个字符串中找到第一个只出现一次的字符
推荐阅读
-
删除排序数组中的重复项
-
JS 对象数组的元素删除,比较对象数组,删除重复对象 JavaScriptJ#HTML
-
JS 对象数组的元素删除,比较对象数组,删除重复对象 JavaScriptJ#HTML
-
数据结构二分法-给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。
-
无序数组中的第k大元素:快速排序和堆排序
-
牛客网刷题java之在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。输入这样的一个二维数组和一个整数,判断数组中是否含有该整数
-
在一个数组中查找两个重复出现两次的数
-
桶排序来实现查找一个无序数组中第k个大的元素
-
在两个排序数组中找第k小的数
-
在一个整数数组中,有一个重复的数字,如何找到重复数字?(请用代码实现)