[Java/C++/Python] O(1) Greedy Solution with Explanation
Solution 1\nGreedily add all element to a result array.\n\nAnyway, greedy solution is not obvious to be right.\nTo handle every continuous elements pair, we act
# **Solution 1**\nGreedily add all element to a result array.\n\nAnyway, greedy solution is not obvious to be right.\nTo handle every continuous elements pair, we actually only care if the number of deleted numbers is even or single.\n\nWe never need to delete a number when not necessary to optimize the deleting in future, because the benefit is at most 1.\nIt doesn\'t worth an early deletion.\n\nTime `O(n)`\nSpace `O(n)`\n<br>\n\n**Python**\n```py\n    def minDeletion(self, A):\n        res = []\n        for a in A:\n            if len(res) % 2 == 0 or a != res[-1]:\n                res.append(a)\n        return len(A) - (len(res) - len(res) % 2)\n```\n<br>\n\n# **Solution 2: Space O(1)**\nUsing a variable `pre` to record the last element with even index.\n\n**Java**\n```java\n    public int minDeletion(int[] A) {\n        int res = 0, pre = -1;\n        for (int a : A) {\n            if (a == pre)\n                res++;\n            else\n                pre = pre < 0 ? a : -1;\n        }\n        return pre < 0 ? res : res + 1;\n    }\n```\n\n**C++**\n```cpp\n    int minDeletion(vector<int>& A) {\n        int res = 0, pre = -1;\n        for (int& a: A) {   \n            if (a == pre)\n                res++;\n            else\n                pre = pre < 0 ? a : -1;\n        }\n        return res + (pre >= 0);\n    }\n```\n**Python**\n```py\n    def minDeletion(self, A):\n        res, pre = 0, -1\n        for a in A:\n            if a == pre:\n                res += 1\n            else:\n                pre = a if pre < 0 else -1\n        return res + (pre >= 0)\n```\n
['C', 'Python', 'Java']