หาตัวเลขซ้ำในอนุกรม n พจน์แรกใน JavaScript

สมมติว่าเราได้รับอาร์เรย์ตัวเลขที่มี n จำนวนธรรมชาติแรก แต่มีสมาชิกหนึ่งปรากฏสองครั้ง ทำให้รวมเป็น n+1 สมาชิก หน้าที่คือเขียนฟังก์ชันรับอาร์เรย์ คืนตัวเลขที่ซ้ำในเวลาเชิงเส้น

วิธี 1: ใช้ Array.prototype.reduce()

วิธีนี้ซับซ้อนนิดหน่อย แต่เขียนโค้ดสั้นที่สุด โค้ด

const arr = [1,4,8,5,6,7,9,2,3,7];
const duplicate = a => a.reduce((acc, val, ind) => val+acc- (ind+1))+a.length-1;
console.log(duplicate(arr));

เราใช้ reduce callback ทำงานหนึ่งครั้งต่อสมาชิก รับสามอาร์กิวเมนต์

• acc → accumulator ค่าที่คืนจากรอบก่อน
• val → ค่าสมาชิกปัจจุบัน
• ind → index ของสมาชิกปัจจุบัน

นำโค้ดไปใช้กับอาร์เรย์นี้

[ 2, 3, 1, 2]

ความยาวอาร์เรย์คือ 4 ควรมี 4 รอบ แต่เราไม่ได้ระบุ initialValue ให้ reduce() ดังนั้นการวนเริ่มจาก index 1 และ accumulator เริ่มต้นเป็นค่าที่ index 0 ดังนั้นมี 3 รอบ

รอบแรก

acc = 2, val = 3, ind = 1 return value = 2+3 - (1+1) = 3

รอบที่สอง

acc = 3, val = 1, ind = 2 return value = 3+1 - (2+1) = 1

รอบที่สาม

acc = 1, val = 2, ind = 3 return value = 1+2 - (3+1) = -1

จบอาร์เรย์

ดังนั้น -1 ถูกคืนจากอาร์เรย์ และจากนั้น

-1 + (4-1) = -1 + 3 = 2

ถูกคืนจากฟังก์ชัน duplicate() ซึ่งเป็นผลลัพธ์ที่ถูกต้อง

วิธี 2: Array.prototype.forEach()

ในวิธีนี้ เราวนลูปอาร์เรย์ หาผลรวม และลบผลรวมของ n-1 จำนวนธรรมชาติแรกออก โดย n คือความยาวอาร์เรย์ สิ่งที่เหลือคือตัวเลขที่ซ้ำสองครั้ง คืนค่านั้น

ตัวอย่าง

const arr = [1,4,8,5,6,7,9,2,3,7];
const duplicate = a => {
  let sum = 0;
  const { length: n } = a;
  a.forEach(num => sum += num);
  return sum - ((n*(n-1))/2);
}
console.log(duplicate(arr));

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็น

7