80号题求有没有更快的答案

Question

最多保留两个元素。

我的实现是用递归，当发现有第三个重复元素时，递归调用查找第一个不重复的元素，从这个元素开始如果发现第三个重复的元素，继续向后查找，剩余个数保存在传进的变量中，函数的返回值返回的就是上一个元素需要连接的索引。

比如数组：{1,1,1,2,2,2,2,3,3,4,5}；

count记录重复次数。当count为3时，就找到了需要覆盖的地方。第一次找到的元素索引是2，值为1，向后查找第一个与1不同的元素，即3号元素，先予以保存索引，然后查找值为2的重复元素，当索引为5时，count为3，又继续向后查找，索引为7, 7后面没有最大重复3个的就开始返回。数组从{1,1,1,2,2,3,3,4,5}变成{1,1,2,2,3,3,4,5}，如果不考虑递归本身的多余消耗，自以为这样比迭代向后查找每次要移动大量可能会被删除的元素要快。不知有没有更好？

代码补充：

#include <iostream>
using namespace std;

int sort( int arr[], int l, int r, int *n )
{
    int tmp=l, tmp_s=l, i=l+1, count = 1;
    while( i<=r && count<3 ){
        if( arr[i] == arr[tmp] ) ++count;
        else{
            count=1;
            tmp=i;
            if( tmp_s == l )
                tmp_s=i;
        }
        ++i;
    }
    if( count==3 ){
        --i;
        count = sort( arr, i, r, n );
        if( tmp_s == l )
            tmp_s = i;
        while( count<=r ) arr[i++] = arr[count++];
        *n-=count-i;
        return tmp_s;
    }
    else{
        if( tmp_s != l ) return tmp_s;
        else return r+1;
    }
}

int main()
{
    int n[]{1,1,1,2,2,3,3,3,4,5,5,6,6,6,6,6,6,6,7,8}, num=sizeof(n)/sizeof(int), total=num;
    sort(n, 0, num-1, &total );
    num = total;
    cout<<"剩余"<< num <<"个: [ ";
    for( int i=0 ; i<num ; ++i ){
        cout<<n[i];
        if( i!=num-1 ) cout<<',';
        else cout<<" ]"<<endl;
    }if( !num ) cout<<" ]"<<endl;
}

不太规范- -悠着点看

Answer 1

liuyubobobo 2017-07-24 14:54:49

请先将你的代码整理成leetcode的格式，在leetcode上首先获得Accepted，我们再来谈论性能效率的问题：）

• 提问者 易萧 #1

  好吧leetcode给那个函数原型递归实现不了  /笑哭/笑哭

• liuyubobobo 回复 提问者 易萧 #2

  可以在Solution类中创建新的成员函数实现递归，也可以继续往后看，后面复杂的问题，我们会经常创造递归的：）

• 提问者 易萧 回复 liuyubobobo #3

  好像有道理啊 - -！

点开查看后面2条评论

Answer 2

agjsytt 2020-03-26 13:22:26

顺着波波老师的思路，我想到了这个解法。并且我还发现个规律，对于视频里提到的4道涉及数组中需要移除某些元素的题目，就是定义一个结果数组[0,k)或[0,k]就能做了。

有些题解称其为双指针，我觉得不太合理，其实就是增加了个逻辑上的结果数组。

func removeDuplicates(nums []int) int {
    k := 1 // [0,k] 存放需要保留的元素。初始化k=1，因为[0,1]是肯定需要放入数组中的
    for i:=2;i<len(nums);i++{
        if nums[i] != nums[k-1]{
            k++
            nums[k] = nums[i]
        }
    }
    return k+1
}

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/solution/xing-shi-shang-lei-si-shuang-zhi-zhen-dan-shi-luo-/

Answer 3

liuyubobobo 2017-07-24 05:35:56

很好的思考，把你的程序写出来试试看？我个人认为思路虽然很好，但是复杂了，在大数据量下，应该是使用迭代的方式更快。但是没有验证不好说，需要具体试验一下：）

另外，看完第四章的内容，回头看这个问题，看能不能使用查找表解决？

加油！

• 提问者 易萧 #1

  写是写出来了不太好懂因为命名规范和变量使用都不规范，比如为了节省一个变量我把计数用的count后面又用在了接受一个索引。  
    我在上面把代码补充出来。
  不过从操作次数上来说，迭代会操作得更多才对吧。