一道有意思的题目 -- Duplicate Zeros

赚小钱

Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.
Note that elements beyond the length of the original array are not written.
Do the above modifications to the input array in place, do not return anything from your function.

Example 1:

1. Input: [1,0,2,3,0,4,5,0]
   
2. Output: null
   
3. Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

复制代码

Example 2:

1. Input: [1,2,3]
   
2. Output: null
   
3. Explanation: After calling your function, the input array is modified to: [1,2,3]

复制代码

Note:

• 1 <= arr.length <= 10000
• 0 <= arr[i] <= 9
  

测试

输入

1. [1,0,2,3,0,4,5,0]
   
2. [1, 0, 0, 0]
   
3. [1, 1, 1, 1]
   
4. [1, 0, 0, 1]
   
5. [1, 1, 1, 0]
   
6. [1, 0, 0, 0, 0]
   
7. [1, 1, 1, 1, 0]
   
8. [1, 0, 0, 1, 0]
   
9. [1, 1, 1, 0, 0]
   
10. [1, 0, 0, 0, 1]
    
11. [1, 1, 1, 1, 1]
    
12. [1, 0, 0, 1, 1]
    
13. [1, 1, 1, 0, 1]

复制代码

输出

1. [1,0,0,2,3,0,0,4]
   
2. [1,0,0,0]
   
3. [1,1,1,1]
   
4. [1,0,0,0]
   
5. [1,1,1,0]
   
6. [1,0,0,0,0]
   
7. [1,1,1,1,0]
   
8. [1,0,0,0,0]
   
9. [1,1,1,0,0]
   
10. [1,0,0,0,0]
    
11. [1,1,1,1,1]
    
12. [1,0,0,0,0]
    
13. [1,1,1,0,0]

复制代码

进阶1
空间复杂度 O(1)。

进阶2
时间复杂度 O(n)。

https://leetcode.com/problems/duplicate-zeros

MIke_python小小

你是英国人吗

sunrise085

有点意思。不过很简单啊
我用python

1. def funnyfun(list1): #时间复杂度 O(n)
   
2.     list2=list()
   
3.     for each in list1:
   
4.         list2.append(each)
   
5.         if len(list1)==len(list2):
   
6.             return list2
   
7.         if each == 0:
   
8.             list2.append(each)
   
9.         if len(list1)==len(list2):
   
10.             return list2
    
11. 
    
12. def funnyfun2(list1): #时间复杂度 O(1)
    
13.     return eval(str(list1).replace('0','0,0'))[:len(list1)]
    
14.    
    
15. list1=eval(input("Input: "))
    
16. print(list1)
    
17. print("Output:",funnyfun(list1))
    
18. print("Output:",funnyfun2(list1))

复制代码

赚小钱

sunrise085 发表于 2020-5-12 10:35
有点意思。不过很简单啊
我用python

亲，这道题一定没有 O(1) 的时间复杂度算法。

觉得简单，可以挑战一下空间复杂度 O(1) 的实现。