การคูณก่อนหน้าและถัดไป  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคเซนเจอร์ แอคโคไลท์ อะโดบี ข้อเท็จจริง UHG Optum
แถว

คำชี้แจงปัญหา  

การคูณก่อนหน้าและถัดไป: ในรูปแบบ แถว แทนที่ทุกองค์ประกอบด้วยผลคูณขององค์ประกอบถัดไปและก่อนหน้านี้ และสำหรับองค์ประกอบแรก (a [0]) เราจำเป็นต้องแทนที่ด้วยผลคูณของถัดไปและตัวมันเองสำหรับองค์ประกอบสุดท้าย (a [n-1]) เราจำเป็นต้องแทนที่ด้วยผลคูณของก่อนหน้าและตัวมันเอง)

ตัวอย่าง  

อินพุต

9

4 8 6 9 12 2 43 2

เอาท์พุต

32 24 72 72 18 516 4 43

อัลกอริทึมสำหรับการคูณก่อนหน้าและถัดไป  

ขั้นตอนที่ 1: สร้างตัวแปรเพื่อเก็บองค์ประกอบก่อนหน้าของอาร์เรย์ เรากำลังจัดเก็บสิ่งนี้โดยที่ไม่มีการใช้พื้นที่เพิ่มเติม
ก) องค์ประกอบแรกจะเป็นผลคูณของตัวแรกและตัวที่สอง
b) องค์ประกอบถัดไปจะเป็นผลคูณของก่อนหน้าและถัดไป

ขั้นตอนที่ 2: สร้างตัวแปร temp dummy เพื่อจัดเก็บก่อนหน้านี้ หลังจากจัดเก็บก่อนหน้านี้ใน temp ให้อัปเดตก่อนหน้าด้วยองค์ประกอบปัจจุบัน หลังจากจัดเก็บปัจจุบันในก่อนหน้านี้ให้อัปเดตอุณหภูมิคูณองค์ประกอบปัจจุบันและองค์ประกอบถัดไปของอาร์เรย์
ก) เรากำลังอัปเดตองค์ประกอบก่อนหน้านี้ก่อนที่จะอัปเดตปัจจุบันดังนั้นเราจึงเก็บค่าไว้ในอุณหภูมิเพื่อที่เราจะไม่สูญเสียคุณค่าของมัน
b) เราอัปเดตก่อนหน้าด้วยองค์ประกอบปัจจุบันเนื่องจากองค์ประกอบถัดไปเป็นปัจจุบัน

ดูสิ่งนี้ด้วย
พิมพ์ subarrays ทั้งหมดด้วยผลรวม 0

ขั้นตอนที่ 3: องค์ประกอบสุดท้ายจะเป็นผลคูณของสุดท้ายและก่อนหน้า

ขั้นตอนที่ 4: พิมพ์อาร์เรย์เพื่อดูว่ามีการอัปเดตหรือไม่

การดำเนินงาน  

โปรแกรม C ++ สำหรับการคูณก่อนหน้าและถัดไป

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int prev=a[0],temp; // previous element to be stored so that no extra space is used.
  a[0]=a[0]*a[1];
  cout<<a[0]<<"  ";
  for(int i=1;i<n-1;i++)
  {
    temp=prev;
    prev=a[i];//set previous to this element
    a[i]=a[i+1]*temp; // multiply prev and forward element
    cout<<a[i]<<"  ";
  }
  a[n-1]=a[n-1]*prev;
  cout<<a[n-1];
  return 0;
}

โปรแกรม Java สำหรับการคูณก่อนหน้าและถัดไป

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int prev=arr[0],temp; // previous element to be stored so that no extra space is used.
        arr[0]=arr[0]*arr[1];
        System.out.print(arr[0]+"  ");
        for(int i=1;i<n-1;i++)
        {
          temp=prev;
          prev=arr[i];//set previous to this element
          arr[i]=arr[i+1]*temp; // multiply prev and forward element
          System.out.print(arr[i]+"  ");
        }
        arr[n-1]=arr[n-1]*prev;
        System.out.println(arr[n-1]);
    }
}
5
1 2 3 4 5
2  3  8  15  20

การวิเคราะห์ความซับซ้อนสำหรับการคูณก่อนหน้าและถัดไป  

ความซับซ้อนของเวลา

O (n) โดยที่ n คือความยาวของอาร์เรย์ที่กำหนด ที่นี่เราจะวนซ้ำผ่านอาร์เรย์ที่กำหนดและคำนวณผลลัพธ์ของเราซึ่งนำเราไปสู่ความซับซ้อนของเวลาเชิงเส้น

ความซับซ้อนของอวกาศ

O (1) เนื่องจากเราใช้ตัวแปรเพียงไม่กี่ตัวในการจัดเก็บค่าก่อนหน้าและคำตอบสำหรับแต่ละดัชนี

อ้างอิง