擅长:python、mysql、java
<p>代码的时间复杂度是<strong>O(M*N)</strong>-<em>,因为您正在搜索<code>arr1</code>中是否有一个匹配的项来匹配<code>arr2</code>中的每个项</em></p>
<p>更好的方法是使用<code>Count</code>数组,并在线性时间和恒定空间中求解它</p>
<p>此代码的复杂性:</p>
<ul>
<li><strong>时间复杂度:O(M+N)</strong></li>
<li><strong>空间复杂性:O(26)</strong></li>
</ul>
<pre><code>arr1 = ["A", "B", "C", "D", "E", "F"]
arr2 = ["C", "A"]
def check(arr1, arr2):
c1 = [0]*26
c2 = [0]*26
a = ord('A')
for i in arr1:
if c1[ord(i) - a] == 0:
c1[ord(i) - a] += 1
for j in arr2:
if c2[ord(i) - a] == 0:
c2[ord(j) - a] += 1
for i in range(len(c1)):
if c2[i] > c1[i]:
return 'Not a Subset'
return 'Subset'
print(check(["A", "B", "C", "D", "E", "F"], ["C", "A"]))
print(check(["B"], ["A", "B"]))
print(check(["A"], ["A", "A"]))
print(check(["A","B"], []))
print(check([], []))
</code></pre>
<pre><code>Subset
Not a Subset
Subset
Subset
Subset
</code></pre>