ปริศนาอาร์เรย์ผลิตภัณฑ์ใน C ++?

ที่นี่เราจะเห็นปัญหาหนึ่งที่น่าสนใจเกี่ยวกับอาร์เรย์ มีอาร์เรย์ที่มีองค์ประกอบ n เราต้องสร้างอาร์เรย์ขององค์ประกอบ n อีกชุดหนึ่ง แต่ตำแหน่งที่ i ของอาร์เรย์ที่สองจะเก็บผลคูณขององค์ประกอบทั้งหมดของอาร์เรย์แรก ยกเว้นองค์ประกอบที่ i และข้อจำกัดอย่างหนึ่งคือเราไม่สามารถใช้ตัวดำเนินการหารในปัญหานี้ได้

ถ้าเราสามารถใช้การหาร การดำเนินการ เราก็สามารถแก้ปัญหานี้ได้ง่ายๆ โดยหาผลคูณขององค์ประกอบทั้งหมด จากนั้นแบ่งองค์ประกอบที่ i ของอาร์เรย์ที่หนึ่งและจัดเก็บไว้ในตำแหน่งที่ i ของอาร์เรย์ที่สอง

ที่นี่ เรากำลังแก้ปัญหานี้โดยสร้างสองอาร์เรย์แยกกัน ด้านซ้ายและขวา left[i] จะเก็บผลคูณขององค์ประกอบทั้งหมดทางด้านซ้ายของ array[i] ยกเว้น array[i] และ right[i] จะเก็บผลคูณขององค์ประกอบทั้งหมดทางด้านขวาของ arr[i] ยกเว้น arr[i] วิธีแก้ปัญหานี้จะใช้เวลา O(n) แต่จะใช้พื้นที่เพิ่มเติม

อัลกอริทึม

productArray(arr, n)

begin
   define two arrays left and right of size n
   define an array called res of size n
   the first element of left and last element of right is set as 1
   for i in range 1 to n, do
      left[i] = left[i-1] * arr[i-1]
   done
   for i in range n-1 down to 1, do
      right[i] = right[i+1] * arr[i+1]
   done
   for i in range 1 to n, do
      res[i] = left[i] * right[i];
   done
   return res
end

ตัวอย่าง

#include<iostream>
using namespace std;
void printArray(int arr[], int n) {
   for(int i = 0; i<n; i++) {
      cout << arr[i] << " ";
   }
   cout << endl;
}
void productArray(int arr[], int product[], int n) {
   //create left right array
   int *left = new int[sizeof(int)*n];
   int *right = new int[sizeof(int)*n];
   //set the first element of left[] and last element of right[] as 1
   left[0] = right[n-1] = 1;
   for(int i = 1; i<n; i++) {
      left[i] = left[i-1] * arr[i-1];
   }
   for(int i = n-2; i>=0; i--) {
      right[i] = right[i+1] * arr[i+1];
   }
   //get product array using left and right array
   for(int i = 0; i<n; i++) {
      product[i] = left[i] * right[i];
   }
}
main() {
   int myArr[7] = {5, 4, 7, 6, 9, 2, 3};
   int resArr[7];
   cout << "Initial Array: ";
   printArray(myArr, 7);
   productArray(myArr, resArr, 7);
   cout << "Final Array: ";
   printArray(resArr, 7);
}

ผลลัพธ์

Initial Array: 5 4 7 6 9 2 3
Final Array: 9072 11340 6480 7560 5040 22680 15120