删除升序数组的重复元素(二)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int removenums(vector<int>& nums) {
        // write code here
        unordered_map<int, int> m;
        for(int i=0; i<nums.size(); i++){
            m[nums[i]]++;
        }
        for(int j=nums.size()-1; j>=0; j--){
            if(m[nums[j]] >= 3){
                m[nums[j]]--;
                nums.erase(nums.begin()+j);
            }
        }
        return nums.size();
    }
};

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/5b617a77d7654dc193bfe5c2bdaf5cc8?tpId=196&tqId=40525&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        使用i、j分别表示已调整数组的尾部+1，当前访问的元素下标；使用candidate和count分别统计当前元素以及出现次数
        初始：
            i, j = 1, 1
            candidate, count = nums[0], 1
        遍历nums：
            对于nums[i]，若等于candidate：
                count += 1
                if count == 3:
                    continue
            否则：
                重新选取candidate = nums[i]
                count = 1
            nums[i] = candidate
            i += 1
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(1)
    """

    def removenums(self, nums):
        # write code here
        n = len(nums)

        i, j = 1, 1
        candidate, count = nums[0], 1

        while j < n:
            if nums[j] == candidate:  # 当nums[j]与当前候选人相等，count+1
                count += 1
            else:  # 不相等时，重新选取候选人
                candidate = nums[j]
                count = 1
            j += 1
            if count > 2:  # 一个候选人，只统计2次
                continue
            nums[i] = candidate
            i += 1

        # print nums[:i]
        return i


if __name__ == "__main__":
    sol = Solution()

    # nums = [1, 1, 2, 2, 3]

    nums = [1, 1, 1, 2, 2, 2, 3, 3]

    m = sol.removenums(nums)

    print nums[:m]