026_从排序数组中删除重复项
本帖最后由 风扫地 于 2019-5-7 21:09 编辑/*
给定一个[排序数组]，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成.
示例 1:
给定数组 nums = ,
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = ,
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums);
}
*/
解法。
/*
基本思想:
把数组分为两个部分:
第一部分:已经没有重复项的部分(由num开始)
第二部分:可能还有重复性的部分
逐一"消灭"第二部分的元素.
"挤压队列"
*/
#include <stdio.h>
int removeDuplicates(int* nums, int numsSize)
{
intlen = 0;
intinner_count = 0;
inti = 0;
do{
/* 输入参数检查,能直接处理的直接处理*/
if((nums == NULL)
||(numsSize <= 0)
)
{
len = 0;
break;
}
if(numsSize==1)
{
len = 1;
break;
}
len = 1;/* 已经保证数组长度至少为2,len既是长度计数,也指向未进入无重复项区域的元素 */
inner_count = 1;/* 标记已经处理过的原始数组的数据个数 */
while(1)
{
if(nums==nums) /* 本来要遍历0~len-1,但已经确认是"排序数组",只需要比较前一个就可用了*/
{
// 已经索引到原始数组的 已经处理掉count个,覆盖一个相当于尾巴去掉一个,所以 i = [0,numsSize - inner_count - 1)
for( i = 0; i < numsSize - inner_count - 1 ; i++ ) /*挪动可能还有重复数的部分,使得(nums+len)指向下一个要判断的元素*/
{
nums = nums;
}
}
else
{
len++;/* 纳入已经没有重复项的部分 */
}
inner_count++;/* */
if(inner_count > numsSize - 1)
{
break;
}
};
break;
}while(0);
return len;
}
测试代码
int main(void)
{
int nums = {112,112,113,114,115};
int len = removeDuplicates(nums,4);// 那么这样，arr 和 arr 应该可用保持不变(只读不写)
for(int i = 0;i<5;i++)
{
printf("%d\n",nums);
}
return 0;
}
/*
161 / 161 个通过测试用例
状态：通过
执行用时 : 504 ms, 在Remove Duplicates from Sorted Array的C提交中击败了9.31% 的用户
内存消耗 : 9.8 MB, 在Remove Duplicates from Sorted Array的C提交中击败了74.91% 的用户
执行耗时爆表了.
*/ 时间效率差远了~还得想想办法。 本帖最后由 jackz007 于 2019-5-8 03:54 编辑
楼主看看这个代码如何
#include <stdio.h>
int removeDuplicates(int * nums , int numsSize)
{
int d , i , k ;
bool f ;
d = 0 ;
if(nums != NULL && numsSize > 0) {
for(d = 1 , i = 1 ; i < numsSize ; i ++) {
for(f = false , k = 0 ; k < d ; k ++) {
if(nums == nums) {
f = true ;
break ;
}
}
if(! f) nums = nums ;
}
}
return d ;
}
int main(void)
{
int b[] = {0 , 1 , 1 , 1 , 2 , 2 , 3 , 3 , 4 , 4 , 5 , 5} , k , m ;
m = removeDuplicates(b , 12) ;
for(k = 0 ; k < m ; k ++) printf("%d\n" , b) ;
}
jackz007 发表于 2019-5-8 03:20
楼主看看这个代码如何
161 / 161 个通过测试用例
状态：通过
执行用时：376 ms
执行用时 : 376 ms, 在Remove Duplicates from Sorted Array的C提交中击败了13.23% 的用户
内存消耗 : 9.6 MB, 在Remove Duplicates from Sorted Array的C提交中击败了74.98% 的用户
赛高，效率比我的提高了接近了一倍~ 受楼上启发：
int removeDuplicates(int* nums, int numsSize)
{
intlen = 0;
intinner_count = 0;
inti = 0;
do{
/* 输入参数检查,能直接处理的直接处理*/
if((nums == NULL)
||(numsSize <= 0)
)
{
len = 0;
break;
}
if(numsSize==1)
{
len = 1;
break;
}
len = 1;/* */
inner_count = 1;
while(1)
{
if(nums != nums)
{
nums = nums;
len++;
}
inner_count++;/* */
if(inner_count > numsSize - 1)
{
break;
}
};
break;
}while(0);
return len;
}
执行用时 : 32 ms, 在Remove Duplicates from Sorted Array的C提交中击败了73.08% 的用户
内存消耗 : 9.7 MB, 在Remove Duplicates from Sorted Array的C提交中击败了74.91% 的用户
页:
[1]