[Leetcode] 2475. Number of Unequal Triplets in Array (Easy)

概述

題目

https://leetcode.com/problems/number-of-unequal-triplets-in-array/
給定一數組，求其中取三數皆不相等之數量

心得

雖然是掛 Easy 且 BF 能解，但第一次看到一種題目至少四種時間複雜度…也是很特別 XD

BF + Set

思路

依序取出後看其集合數量是否為 3，若是則表示三數無兩兩相等，反之則有，算是總組數即可

程式

class Solution(object):
    def unequalTriplets(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        cnt = 0
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1, n):
                    if len(set([nums[i], nums[j], nums[k]])) == 3:
                        cnt += 1
        return cnt

Complexity

Time Complexity: O(n^3)
最多走過三次 n 個數字

Space Complexity: O(1)
無使用額外空間

Counter

思路

算出每個數出現次數，再三三一組確認符合題意的組合有多少個

程式

class Solution(object):
    def unequalTriplets(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = Counter(nums)
        if len(dic) < 3:
            return 0

        n = len(dic)
        arr = [b for a, b in dic.items()]
        cnt = 0
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1, n):
                    cnt += arr[i]*arr[j]*arr[k]
        return cnt

Complexity

Time Complexity: O(n^3)
最多走過三次 n 個數字

Space Complexity: O(n)
dic 最多可有 n 個不同數

O(n^2)

思路

找出兩數後確認第三數不相同，計算總數組數量

程式

class Solution(object):
    def unequalTriplets(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = Counter(nums)
        n = len(dic)
        if n < 3:
            return 0
        
        arr = [b for a, b in dic.items()]

        cnt = 0
        tot = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                cnt += arr[i] * arr[j] * (tot-arr[i]-arr[j])

        # 固定兩個數，第三個數可能是皆小於、介於中間、都大於，三種可能性
        return cnt // 3

Complexity

Time Complexity: O(n^2)
最多走過兩次 n 個數字

Space Complexity: O(n)
dic 最多可有 n 個不同數

O(n log n)

思路

from theabbie ，先排序，而後切成大於、等於、小於三群類，再計算不同群各取一數之數量

程式

class Solution(object):
    def unequalTriplets(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        nums.sort()
        cnt = 0
        i = 0
        while i < n:
            # ctr 表示有幾個數是相等、i-ctr 表小於該數可能性、n-i 表大於該數可能性
            ctr = 1
            while i < n - 1 and nums[i] == nums[i + 1]:
                ctr += 1
                i += 1
            i += 1
            cnt += (i - ctr) * ctr * (n - i)
        return cnt

Complexity

Time Complexity: O(n log n)
先排序

Space Complexity: O(n)
dic 最多可有 n 個不同數

O(n)

思路

from lee215 大神，想法上可以先從取 2 個不同數的總數組數量開始：走過一次 n 個數字，每次只會回頭看前面已經走過的數字是否有不可以 pair 的，若是有，則由現在位置的數量去減掉重覆的數量，即是可 pair 的數字，其實思路上與 O(n log n) 類似

以下範例 code 中的 a function 是 O(n) 的枚舉

from random import randint
from collections import Counter

class Solution(object):
    def a(self, nums):
        dic = Counter(nums)
        cnt = 0
        tot = len(nums)
        for c in dic:
            cnt += dic[c] * (tot - dic[c])
        return cnt // 2

    def b(self, nums):
        pairs = 0
        dic = Counter()
        # 向前確認是否可 pair
        for i, a in enumerate(nums):
            pairs += i - dic[a]
            dic[a] += 1
        return pairs


def main():
    k = 1000
    for i in range(k):
        nums = [randint(1,k) for i in range(k)]
        if Solution().a(nums) != Solution().b(nums):
            print(Solution().a(nums) == Solution().b(nums), Solution().a(nums), Solution().b(nums))

if __name__ == '__main__':
    main()

同理，將 2 個數推廣至 3 個數，則程式如下：

程式

class Solution(object):
    def unequalTriplets(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        trips = pairs = 0
        dic = Counter()
        for i, a in enumerate(nums):
            # 再向前確認可 pair 的部分是否存在不可 trips 的狀況
            trips += pairs - dic[a] * (i - dic[a])
            # 向前確認是否可 pair
            pairs += i - dic[a]
            dic[a] += 1
        return trips

Complexity

Time Complexity: O(n)
最多走過 n 個數字

Space Complexity: O(n)
dic 最多可有 n 個不同數

Follow Up

4 數組

若是 4 數組的情況，一樣可直接擴增

程式

from random import randint
from collections import Counter

class Solution(object):
    def a(self, nums):
        n = len(nums)
        cnt = 0
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1, n):
                    for l in range(k+1, n):
                        # print(nums[i], nums[j], nums[k], nums[l])
                        if len(set([nums[i], nums[j], nums[k], nums[l]])) == 4:
                            cnt += 1
        return cnt

    def b(self, nums):
        fours = trips = pairs = 0
        dic = Counter()
        for i, a in enumerate(nums):
            fours += trips - dic[a] * (i - dic[a])
            trips += pairs - dic[a] * (i - dic[a])
            pairs += i - dic[a]
            dic[a] += 1
        return fours


def main():
    k = 10
    for i in range(k):
        # nums = [randint(1,k) for i in range(k)]
        nums = [j for j in range(i+4)]
        # print(nums)
        if Solution().a(nums) != Solution().b(nums):
            print(Solution().a(nums) == Solution().b(nums), Solution().a(nums), Solution().b(nums))


if __name__ == '__main__':
    main()

5 數組

相同作法擴增

程式

from random import randint
from collections import Counter

class Solution(object):
    def a(self, nums):
        n = len(nums)
        cnt = 0
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1, n):
                    for l in range(k+1, n):
                        for m in range(l+1, n):
                        # print(nums[i], nums[j], nums[k], nums[l], nums[m])
                            if len(set([nums[i], nums[j], nums[k], nums[l], nums[m]])) == 5:
                                cnt += 1
        return cnt

    def b(self, nums):
        fives = fours = trips = pairs = 0
        dic = Counter()
        for i, a in enumerate(nums):
            fives += fours - dic[a] * (i - dic[a])
            fours += trips - dic[a] * (i - dic[a])
            trips += pairs - dic[a] * (i - dic[a])
            pairs += i - dic[a]
            dic[a] += 1
        return fives


def main():
    k = 10
    for i in range(k):
        # nums = [randint(1,k) for i in range(k)]
        nums = [j for j in range(i+5)]
        # print(nums)
        if Solution().a(nums) != Solution().b(nums):
            print(Solution().a(nums) == Solution().b(nums), Solution().a(nums), Solution().b(nums))


if __name__ == '__main__':
    main()