สมมติว่าเราได้ให้อาร์เรย์ของจำนวนเต็มที่ไม่เรียงลำดับ ภารกิจคือการค้นหาจำนวนบวกที่ขาดหายไปซึ่งไม่มีอยู่ในอาร์เรย์ที่กำหนดในช่วง [0 ถึง n] ตัวอย่างเช่น
อินพุต-1 −
N = 9 arr = [0,2,5,9,1,7,4,3,6]
ผลผลิต −
8
คำอธิบาย − ในอาร์เรย์ที่ไม่เรียงลำดับที่กำหนด '8' เป็นจำนวนเต็มบวกเพียงจำนวนเดียวที่ขาดหายไป ดังนั้นเอาต์พุตจึงเป็น '8'
อินพุต-2 −
N = 1 arr = [0]
ผลผลิต −
1
คำอธิบาย − ในอาร์เรย์ที่กำหนด '1' เป็นจำนวนเต็มบวกเพียงจำนวนเดียวที่ขาดหายไป ดังนั้นเอาต์พุตจึงเป็น '1'
แนวทางการแก้ปัญหานี้
มีหลายวิธีในการแก้ปัญหานี้โดยเฉพาะ อย่างไรก็ตาม เราสามารถแก้ปัญหานี้ได้ในเวลาเชิงเส้น O(n) และปริภูมิคงที่ O(1)
เนื่องจากเรารู้ว่าอาร์เรย์ของเรามีขนาด n และมีองค์ประกอบอยู่ในช่วง [0 ถึง n] ดังนั้น หากเราดำเนินการ XOR ของแต่ละองค์ประกอบและดัชนีขององค์ประกอบด้วย 'n' เราจะสามารถหาจำนวนผลลัพธ์เป็นตัวเลขเฉพาะที่ขาดหายไปจากอาร์เรย์
-
รับอินพุตขนาด N ของอาร์เรย์ที่มีองค์ประกอบอยู่ในช่วง [0 ถึง n]
-
ฟังก์ชันจำนวนเต็ม findMissingNumber(int arr[], int size) รับอาร์เรย์และขนาดเป็นอินพุตและส่งกลับตัวเลขที่หายไป
-
เอาล่ะ n เป็นตัวเลขที่ขาดหายไปเพื่อดำเนินการ XOR
-
วนซ้ำองค์ประกอบอาร์เรย์ทั้งหมดและดำเนินการ XOR กับองค์ประกอบอาร์เรย์แต่ละรายการและดัชนีที่เกี่ยวข้องกับตัวเลขที่ขาดหายไป เช่น n
-
ตอนนี้ส่งคืนหมายเลขที่หายไป
ตัวอย่าง
public class Solution {
public static int findMissingNumber(int arr[], int size){
int missing_no= size;
for(int i=0;i<size;i++){
missing_no^= i^arr[i];
}
return missing_no;
}
public static void main(String[] args){
int arr[] = {0,4,2,1,6,3};
int n = arr.length;
int a=findMissingNumber(arr, n);
System.out.println(a);
}
} ผลลัพธ์
การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
5
ในอาร์เรย์ที่กำหนด {0,4,2,1,6,3} ไม่มี '5' ดังนั้นเราจะคืนค่า 5
