หาคู่ตัวเลขที่ตัวหนึ่งเป็น 3 เท่าอีกตัวใน Python

ภาพรวม

โจทย์ตรวจสอบว่ามีคู่ตัวเลขในลิสต์ที่ตัวหนึ่งเป็น 3 เท่าของอีกตัว (x และ 3x) หรือไม่

ตัวอย่าง

อินพุต: [2, 3, 10, 7, 9]

เรียง: [2, 3, 7, 9, 10]

3 × 3 = 9 → พบคู่ (3, 9) → True

อัลกอริทึม Two Pointers

1. เรียงลิสต์
2. i=0, j=1
3. ถ้า 3×nums[i] == nums[j] → พบ
4. ถ้า 3×nums[i] > nums[j] → j++ (ต้องการค่ามากขึ้น)
5. ถ้า 3×nums[i] < nums[j] → i++ (ลดค่าเป้าหมาย)

โค้ด Python

class Solution:
    def solve(self, n):
        i = 0
        n.sort()
        j = 1
        while j < len(n):
            if 3 * n[i] == n[j]:
                return True
            if 3 * n[i] > n[j]:
                j += 1
            else:
                i += 1
        return False

ob = Solution()
print(ob.solve([2, 3, 10, 7, 9]))

วิธี Set (ง่ายกว่า O(n))

def has_triple_pair(nums):
    s = set(nums)
    for x in nums:
        if 3 * x in s:
            return True
    return False

ผลลัพธ์

True