Shulou(Shulou.com)06/03 Report--

In this issue, the editor will bring you about how to explain O (1) from a simple algorithm problem in Python. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

Today, a classmate asked an algorithm question in the fan group:

The topics in the dialogue are as follows:

The topic requires that repeated elements be deleted in place from an ordered array nums, so that each element appears only once. Returns the length of the deleted array. You can't use extra array space, use O (1) space complexity.

This student made a mistake because he didn't understand what O (1) space complexity is. He actually generated a new list on line 3. The length of the list depends on the length of the original list. The more elements the original list does not repeat, the longer the new list will be, so its space complexity is O (n). And the title requires "in place" to modify the original list instead of generating a new one.

Let's first talk about what is called O (1) space complexity. It does not mean that you can only apply for one variable, but that the number of additional variables you apply for is constant and does not change according to the number of input list elements. So, even if you apply for 10,000 variables, whether the original list has one element or 100 million elements, you always use only these 10,000 variables, so you can say that the space complexity is O (1).

Let's talk about what is meant by in-situ modification. That is to say, you directly modify the input list without using the new list. We know that in Python, adding an element to the list using xxx.append (yy) and deleting an element xxx.pop (index) from the list according to the index are all modified in place.

Back to this question, this question belongs to the simple level of LeetCode above, if you want to apply for a better Internet company, this kind of question should be easy to come by.

The key to this problem is that the original list is an ordered list, so the repeated numbers must be linked together. Therefore, we just need to check one by one whether the current element is the same as the previous element, if it is the same, remove the current element, and if not, check the next element.

So, let's write the code:

Class Solution: def removeDuplicates (self Nums): if not nums: return 0 last = None index = 0 length = len (nums) while index < length: ele = nums [index] if index = = 0: last = ele index = 1 elif ele = = last: length-= 1 Nums.pop (index) else: last = ele index + = 1 return length

The running effect is shown in the following figure:

It is important to note that the time complexity of this question is O (n), because when you delete elements from the list according to the index, the subsequent elements move forward one bit in turn. Generally speaking, you can't have both time complexity and space complexity. You can trade space for time, or time for space, but it's hard to do it without taking up space and time at the same time.

This is how to explain what is called O (1) from a simple algorithm problem in Python shared by the editor. If you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.