ลบค่าซ้ำในตำแหน่งเดิม
ใช้คู่ตัวชี้ช้าและเร็ว
ลบค่าซ้ำในตำแหน่งเดิม เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ลบค่าซ้ำภายในอาร์เรย์เดิม
เมื่อกำหนดอาร์เรย์ที่ เรียงลำดับแล้ว ให้เก็บค่าละหนึ่งชุดโดยไม่ใช้อาร์เรย์เพิ่มเติม การทำงานภายในอาร์เรย์เดิมช่วยประหยัดหน่วยความจำ และเป็นโจทย์สัมภาษณ์ที่พบบ่อย 🧹
เหตุผลที่การเรียงลำดับช่วยได้
เมื่ออาร์เรย์เรียงลำดับแล้ว ค่าที่ ซ้ำทุกค่าจะอยู่ติดกับค่าที่เหมือนกัน ดังนั้นคุณจึงเปรียบเทียบเฉพาะสมาชิกข้างเคียง ไม่ต้องเปรียบเทียบกับทั้งอาร์เรย์
สองบทบาท สองตัวชี้
ใช้ตัวชี้ ช้าเพื่อระบุตำแหน่งของค่าล่าสุดที่เก็บไว้ และใช้ตัวชี้เร็วเพื่อสแกนไปข้างหน้าเพื่อค้นหาค่าใหม่
slow = 0
fast = 1ตัวชี้ช้าเป็นผู้เขียน
ให้คิดว่าตัวชี้ ช้าเป็นตำแหน่งเขียน ทุกค่าที่อยู่ที่ตำแหน่งนี้หรือต่ำกว่านั้นได้รับการจัดการและไม่ซ้ำกันแล้ว
ตัวชี้เร็วเป็นผู้อ่าน
ตัวชี้ เร็วมีหน้าที่เพียงอ่านไปข้างหน้า มันเร่งนำไปก่อน และจะส่งสัญญาณให้ตัวชี้ช้าเมื่อพบค่าที่ยังไม่ได้เก็บไว้
ข้ามค่าที่ซ้ำ
หาก a[fast] เท่ากับ a[slow] แสดงว่าเป็น ค่าซ้ำ จึงไม่ต้องทำอะไรนอกจากเลื่อน fast ไปข้างหน้า ค่าซ้ำจะถูกข้ามไปอย่างเงียบ ๆ
for fast in range(1, n):
if a[fast] == a[slow]:
continueพบค่าใหม่
เมื่อ a[fast] แตกต่าง ให้เลื่อนตัวชี้ ช้าไปข้างหน้า แล้วคัดลอกค่าใหม่ไปไว้ที่ตำแหน่งนั้น การทำเช่นนี้จะแทนที่ค่าซ้ำเดิมด้วยข้อมูลใหม่ที่ไม่ซ้ำกัน
else:
slow += 1
a[slow] = a[fast]คำตอบคือความยาว
หลังจากสแกนเสร็จ slow + 1 คือจำนวนค่าที่ไม่ซ้ำกัน ซึ่งถูกจัดเรียงรวมไว้ที่ส่วนหน้าของอาร์เรย์
return slow + 1ไม่ต้องสนใจส่วนท้าย
สิ่งที่อยู่ หลังจากส่วนหน้าที่มีค่าไม่ซ้ำกันคือข้อมูลตกค้างที่ไม่จำเป็น โจทย์สนใจเฉพาะสมาชิก slow + 1 ตัวแรก ดังนั้นจึงปล่อยส่วนท้ายไว้ได้
ระวังอาร์เรย์ว่าง
อาร์เรย์ที่ ว่างเปล่ามีค่าที่ไม่ซ้ำกันเป็นศูนย์ ให้ตรวจสอบ n == 0 ก่อนเริ่มทำงาน เพื่อไม่ให้พยายามอ่านข้อมูลเกินขอบเขต
if n == 0:
return 0รอบเดียว ไม่ใช้พื้นที่เพิ่มเติม
รูปแบบตัวชี้ช้าและเร็วนี้ใช้เวลา O(n) และใช้พื้นที่เพิ่มเติม O(1) ซึ่งตรงตามข้อกำหนดของโจทย์ที่มีขีดจำกัดหน่วยความจำเข้มงวด
ตรวจสอบอย่างรวดเร็ว
คุณกำลังลบค่าซ้ำภายในอาร์เรย์เดิมที่เรียงลำดับแล้ว โดยใช้ตัวชี้ช้าและตัวชี้เร็ว
สรุปทบทวน
ในอาร์เรย์ที่เรียงลำดับแล้ว ตัวชี้คู่ ช้าและเร็วจะลบค่าซ้ำได้ในรอบเดียวที่ใช้เวลา O(n) โดยไม่ใช้พื้นที่เพิ่มเติม และส่ง slow + 1 เป็นจำนวนค่าที่ไม่ซ้ำกัน 🎉
คำถามที่พบบ่อย
บทเรียน “ลบค่าซ้ำในตำแหน่งเดิม” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ลบค่าซ้ำในตำแหน่งเดิม” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ลบค่าซ้ำในตำแหน่งเดิม”
ใช้คู่ตัวชี้ช้าและเร็ว คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “ลบค่าซ้ำในตำแหน่งเดิม” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ตัวชี้สองตัวบนอาร์เรย์ที่เรียงแล้ว
- ค้นหาคู่ที่มีผลรวมกำหนด
- ลบค่าซ้ำในตำแหน่งเดิม
- ผสานลำดับที่เรียงแล้วสองชุด