Input: An array of characters, example: [a,a,b,b,b,a,c] Ouput: Smallest length reduced form after removing duplicates step by step: [c]
[a,a,b,b,b,a,c] remove all b> [a,a,a,c] remove all a> [c] [a,b,c,c,b,a,a] remove all c> [a,b,b,a,a] remove all b> [a,a,a] > []
Does anyone know if it's similar to an existing leetcode question? I couldn't find the solution, but interviewer hinted that it's about using a stack.
收藏的用户（0）
X
正在加载信息~
最新回复 (1)

#!/usr/bin/python #* coding:utf8 * """ When you see 'duplicates' related questions you should immediately hint yourself with the most powerful set of data structures that solve this type of problem. Taking Java as an example, typical data structures are HashMap and HashSet which are normally used to count or mark presense of uniqueness. In Python, there are also set() and dict() (i.e., '{}') for you to use. In C, there are bitmap and lookup table. Highly recommend you to understand the principles before you jump to a solution. In this problem, no matter how you reduce the form of the array of characters, you are always removing characters that appear more than once. Since you did not mention clearly if the interviewer wants the reduced array or the list of reduction steps, I assume it's the reduced array. As you listed in your examples: Input: [a,a,b,b,b,a,c] Output: [c] Input: [a,b,c,c,b,a,a] Output: [] On the other hand, you should also ask the interviewer if the original "Array" is mutable or immutable and if extra memory is allowed to allocate to solve this problem. From the hint, it seems a stack solution is possible but not necessary. Stack is used often if the order of something makes a difference to your output. Here the order of the removal steps don't really affect the output. I.e., you can remove all 'a' first or all 'b' first, the output is always [c] in the first example. You can remove all 'a' first, or all 'c' first, or all 'b' first, the output in always [] in the second example. A dict/HashMap solution is way more intutitive. """ """ This solution gives you worst case O(n) time complexity if 'n' is length of the array. Worst case is that all characters are unique in array. This solution allocates O(n) worst case extra memory due to use of dict. Worst case is that all characters are unique in array. """ def reduce_duplicates_dict(arr): # initialize a dict s = {} for i in xrange(0, len(arr)): if arr[i] not in s: s[arr[i]] = 1 else: s[arr[i]] += 1 result = [] for key, value in s.iteritems(): if value < 2: result.append(key) return result if __name__ == "__main__": # using dict print(reduce_duplicates_dict(['a', 'a', 'b', 'b', 'b', 'c'])) print(reduce_duplicates_dict(['a','b','b','a','a']))