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

来源：3-4 即使简单的问题，也有很多优化的思路

易萧

2017-07-23

最多保留两个元素。

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

比如数组：{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;
}

不太规范- -悠着点看

写回答

3回答

liuyubobobo

2017-07-24

已采纳

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

易萧

liuyubobobo

但是只打败了25%的人。好气。算了还是看完查表再说吧

2017-07-25

共5条回复

agjsytt

2020-03-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-/