刚面完的狗狗

求问time complexity

xuantao427 发表于 2019/10/11 11:36:16
求问time complexity

个人觉得最坏时间复杂度可能是O(N), N表示array里最大元素的值。
最坏情况下可能是一个连续序列，比如初始是[5,1], 最后结果是[5,4,3,2,1]。由于hashset存在导致每个元素最多被访问一次。

adayxiang 发表于 2019-10-11 04:06
请问下如果path的路径不同,但是包含的数相同需要去重吗?

如果用 backtracking + hashset可以做吗? hashs ...

这样应该可行，但时间复杂度是不是太高了，每次递归，都要两两相减寻找符合要求的数。

揣摩意思写了一下， 每次dfs只要考虑新加的这一个元素和之前数组里所有元素的差值

1. class Solution:
   
2.     def findPath(self, nums):
   
3.         
   
4.         self.paths = []
   
5.         def helper(nums, n1, path):
   
6.             end = True
   
7.             cur = set()
   
8.             for n2 in nums:
   
9.                 if n1 == n2:
   
10.                     continue
    
11.                 n = abs(n1 - n2)
    
12.                 if n not in nums and n not in cur:
    
13.                     end = False
    
14.                     cur.add(n)
    
15.                     next_nums = nums | set([n])
    
16.                     helper(next_nums, n, path + [next_nums])
    
17.             if end:
    
18.                 self.paths.append(path)
    
19.         helper(set(nums), nums[-1], [])   
    
20.         return self.paths

复制代码

LockOn 发表于 2019-10-12 12:22
揣摩意思写了一下， 每次dfs只要考虑新加的这一个元素和之前数组里所有元素的差值

[mw_shl_code=python, ...

请问可以稍微解释一下吗，不是很看得懂python……

是只要保留最后一个的结果，还是要把这个过程也要return出来？比如说[3, 1]，是要return[3, 1, 2]还是return[[3, 1], [3, 1, 2]]?

OliviaC0209 发表于 2019-10-17 17:33
是只要保留最后一个的结果，还是要把这个过程也要return出来？比如说[3, 1]，是要return[3, 1, 2]还是retur ...

整个过程都要return。 并且要return全部可能的过程

用Java实现了下brute force解法，复杂度太高了，楼主的[17, 3]例子都没跑出来，跑了个[8, 3]，代码和结果如下，大家来讨论下怎么优化吧。。。