首页 > 其他 > 详细

leetcode笔记:Remove Duplicates from Sorted Array II

时间:2015-07-24 18:26:41      阅读:234      评论:0      收藏:0      [点我收藏+]

一.题目描述

技术分享

二.解题技巧

这道题和Remove Duplicates from Sorted Array这道题是类似的,只不过这里允许出现重复的数字而已,可以采用二分搜索的变种算法,只不过加入了剔除和第一个元素相同的元素的过程。另一个思路是加入一个变量,用于记录元素出现的次数。这题因为是已经排序的数组,所以一个变量即可解决。如果是没有排序的数组,则需要引入一个hash表来记录出现次数。

三.示例代码

class Solution {  
public:  

    int RemoveDuplicatesFromStart(int* A, int n)  
    {  
        int NumberOfDuplicates = 0;  
        int Start = A[0];  

        for (int Index = 1; Index < n; Index++)  
        {  
            if ( Start != A[Index])  
            {  
                break;  
            }  

            NumberOfDuplicates++;  
        }  

        return NumberOfDuplicates;  

    }  


    int RemoveDuplicatesFromEnd(int* A, int n)  
    {  
        int NumberOfDuplicates = 0;  
        int Start = A[0];  

        for (int Index = n - 1; Index > 0; Index--)  
        {  
            if (Start != A[Index])  
            {  
                break;  
            }  

            NumberOfDuplicates++;  
        }  

        return NumberOfDuplicates;  
    }  



    bool search(int A[], int n, int target)  
    {  
        if (n < 1)  
        {  
            return false;  
        }  

        if (n == 1)  
        {  
            if (A[0] == target)  
            {  
                return true;  
            }  

            return false;  
        }  

        if (n == 2)  
        {  
            if (A[0] == target)  
            {  
                return true;  
            }  

            if (A[1] == target)  
            {  
                return true;  
            }  
            return false;  
        }  


        if (A[0] == target)  
        {  
            return true;  
        }  

        // remove the duplicates  
        int DuplicatesFromStart = RemoveDuplicatesFromStart(A, n);  

        if (DuplicatesFromStart == (n - 1))  
        {  
            return false;  
        }  


        int DuplicatesFromEnd = RemoveDuplicatesFromEnd(A, n);  

        if (DuplicatesFromEnd == (n - 1))  
        {  
            return false;  
        }  

        n = n - DuplicatesFromStart - DuplicatesFromEnd;  

        if (n < 2)  
        {  
            return false;  
        }  

        A = A + DuplicatesFromStart;  



        if (A[n / 2] == target)  
        {  
            return true;  
        }  

        if (A[0] > target)  
        {  
            if (A[0] < A[n / 2])  
            {  
                return search((A + n / 2), (n - n / 2 ), target);  
            }  

            if (A[n / 2] < target)  
            {  
                return search((A + n / 2), (n - n / 2), target);  
            }  

            return search(A, (n / 2), target);  

        }  
        else  
        {  
            if (A[0] < A[n / 2])  
            {  
                if (A[n / 2] < target)  
                {  
                    return search((A + n / 2), (n - n / 2), target);  
                }  
                return search(A, (n / 2), target);  
            }  
            return search(A, (n / 2), target);  
        }  
    }  
};  

四.体会

以上的算法采用变种的二分搜索算法,只不过是加入了剔除和第一个元素相同的元素的过程,加入了这个过程之后,我使用的方法在最差情况下(所有元素都相同的情况)的时间复杂度为O(n)。

版权声明:本文为博主原创文章,未经博主允许不得转载。

leetcode笔记:Remove Duplicates from Sorted Array II

原文:http://blog.csdn.net/liyuefeilong/article/details/47043441

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!