โปรแกรมหาจำนวนจำนวนเต็มที่ไม่ซ้ำกันในรายการที่เรียงลำดับแล้วด้วย Python

โจทย์

กำหนดให้มีรายการตัวเลขที่เรียงลำดับจากน้อยไปมากแล้ว (nums) ต้องการหาจำนวนของค่าที่ไม่ซ้ำกัน (Unique values) ในรายการนั้น

ตัวอย่าง: หาก nums = [3, 3, 3, 4, 5, 7, 7] ผลลัพธ์คือ 4 เพราะค่าที่ไม่ซ้ำกันคือ [3, 4, 5, 7]

วิธีแก้ปัญหา (Algorithm)

เนื่องจากข้อมูล เรียงลำดับแล้ว สามารถแก้ได้อย่างมีประสิทธิภาพโดยไม่ต้องใช้ Set:

1. ถ้ารายการว่าง ให้คืนค่า 0
2. เริ่มนับจาก 1 (ตัวแรกไม่ซ้ำแน่นอน)
3. วนลูปเปรียบเทียบค่าปัจจุบันกับค่าก่อนหน้า
4. ถต่างกัน ให้เพิ่มจำนวนนับ
5. คืนค่าจำนวนนับสุดท้าย

ซับซ้อนเวลา: O(n) | พื้นที่: O(1) (ไม่ใช้พื้นที่เพิ่ม)

การเขียนโค้ด Python

class Solution:
    def solve(self, nums):
        """
        หาจำนวนค่าที่ไม่ซ้ำกันในลิสต์ที่เรียงลำดับแล้ว
        
        Args:
            nums: List[int] - ลิสต์ตัวเลขที่เรียงจากน้อยไปมาก
            
        Returns:
            int - จำนวนค่าที่ไม่ซ้ำกัน
        """
        if not nums:
            return 0
        
        count = 1  # ตัวแรกนับเป็น 1 เสมอ
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                count += 1
        return count


# ทดสอบการทำงาน
if __name__ == "__main__":
    ob = Solution()
    test_data = [3, 3, 3, 4, 5, 7, 7]
    print(f"Input: {test_data}")
    print(f"Output: {ob.solve(test_data)}")  # ผลลัพธ์: 4

วิธีทางเลือก: ใช้ Set (สำหรับข้อมูลที่ไม่ได้เรียงลำดับ)

def count_unique_set(nums):
    """ใช้ได้กับลิสต์ที่ไม่ได้เรียงลำดับ แต่ใช้พื้นที่ O(n)"""
    return len(set(nums))

# ทดสอบ
print(count_unique_set([3, 3, 3, 4, 5, 7, 7]))  # 4
print(count_unique_set([7, 3, 5, 3, 4, 7, 3]))  # 4 (ไม่ต้องเรียง)

สรุป

สำหรับโจทย์นี้ที่ระบุชัดเจนว่า 「รายการที่เรียงลำดับแล้ว」 วิธี Linear Scan เป็นคำตอบที่เหมาะสมและมีประสิทธิภาพที่สุด