პროდუქტის მასივის თავსატეხი


Რთული ტური საშუალო
ხშირად ეკითხებიან თანამოსაყრელი Adobe Amazon Apple ასანა BlackRock Bloomberg ByteDance ციხედ დე შოუ eBay Evernote- Expedia Facebook Goldman Sachs Google Houzz Intel LinkedIn ლიფტი microsoft Morgan Stanley ნუტუნიქსი ოპერისა Oracle PayPal Paytm Qualtrics Salesforce SAP სერვისი Snapchat გაღრმავება ცხრილი Twitter Uber Visa VMware Walmart Labs Yahoo Yandex
Array Groupon LeetCode

პრობლემის განცხადება

პროდუქტში მასივი თავსატეხი პრობლემა უნდა გვქონდეს ისეთი მასივის შესაქმნელად, სადაც მეth ელემენტი იქნება მოცემული მასივის ყველა ელემენტის პროდუქტი, გარდა i- ის ელემენტისაth პოზიცია.

მაგალითი

შეყვანის 

5

10 3 5 6 2

გამოყვანის

180 600 360 300 900

პროდუქტის მასივის თავსატეხის ამოხსნის ალგორითმი

ნაბიჯი 1: აიღეთ ვექტორული პროდუქტი პროდუქციის შესანახად.
ა) მისი ინიცირება ვექტორული პროდუქტის მიხედვით

ნაბიჯი 2: ააშენეთ ორი მასივი მარცხნივ [] და მარჯვნივ [], მარცხენაში ინახება ელემენტების პროდუქტი მასივის ith ინდექსის მარცხნივ უფლება ინახავს ელემენტების პროდუქტს ith ინდექსის მარჯვნივ.

ა ინიციალეთ მარცხენა პირველი ელემენტი 1-ით და მარჯვენა ბოლო ელემენტით 1-ით.
ბ მარცხნიდან განაახლეთ მარცხენა მასივის ith ელემენტები მოცემული მასივის i-1 ელემენტის პროდუქტით მარცხენა მასივის წინა ელემენტთან. (მარცხნივ [i] = მარცხნივ [i-1] * მასივი [i-1]). ამით, იგი ინახავს პროდუქტს მოცემული მასივის მარცხენა მასივში წინა ინდექსამდე.
გ მარჯვნივ, განაახლეთ მარჯვენა მასივის ith ელემენტები მოცემული მასივის i + 1 ელემენტის პროდუქტით მარჯვენა მასივის შემდეგი ელემენტით. (უფლება [i] = მარჯვენა [i + 1] * მასივი [i + 1]]. ამით, იგი ინახავს პროდუქტს მოცემული მასივის მარცხენა მასივში წინა ინდექსამდე.

ნაბიჯი 3:  პროდუქტი, გარდა წინამდებარე ელემენტისა, იქნება იგივე, რაც მარცხენა და მარჯვენა მასივის ელემენტების პროდუქტი.
ა) პროდუქტის მასივი იქნება, პროდუქტი [i] = მარცხენა [i] * მარჯვნივ [i].

პროდუქტის მასივის თავსატეხის ამოხსნის განმარტება

პირველი, თავიდანვე გადალახეთ მასივი და შეინახეთ ყველა წინა ელემენტის პროდუქტი თითოეული i- სთვის. ახლა გადაკვეთეთ მასივი უკნიდან და შეინახეთ ჯამი ბოლოდან და შეინახეთ ყველა ელემენტის პროდუქტი ამ ელემენტის შემდეგ.

მარცხენა [] = {10, 30, 150, 900, 1800}

მარჯვნივ [] = {1800, 180, 60, 12, 2}

ახლა ამ მასივის გამოყენებით იპოვნეთ მოცემული მასივის ყველა ელემენტის პროდუქტი, გარდა i- ის ელემენტისაth პოზიცია.

პროდუქტი [] = {180, 600, 360, 300, 900}

განხორციელება

C ++ პროგრამა პროდუქტის მასივის თავსატეხის გადასაჭრელად

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  int left[n],right[n];
  vector<int> product;
  left[0] = 1; //initialize the first element as 1
  for(int i=1;i<n;i++)
  {
     left[i]=left[i-1]*arr[i-1]; // store the product till just previous index
  }
  right[n-1]=1;//initialzie the first element as 1
  for(int i=n-2;i>=0;i--)
  {
     right[i]=right[i+1]*arr[i+1]; //store the product till just next index
  } 
  for(int i=0;i<n;i++)
  {
     product.push_back(left[i]*right[i]);
  }
  for(int i=0;i<n;i++)//display the product array
  {
     cout<<product[i]<<"  "; 
  }
  return 0;
}

Java პროგრამა პროდუქტის მასივის თავსატეხის გადასაჭრელად

import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
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 left[] = new int [n];
        int right[] = new int [n];
        Vector<Integer> product = new Vector<Integer>(); 
        left[0] = 1; //initialize the first element as 1
        for(int i=1;i<n;i++)
        {
           left[i]=left[i-1]*arr[i-1]; // store the product till just previous index
        }
        right[n-1]=1;//initialzie the first element as 1
        for(int i=n-2;i>=0;i--)
        {
           right[i]=right[i+1]*arr[i+1]; //store the product till just next index
        } 
        for(int i=0;i<n;i++)
        {
           product.add(left[i]*right[i]);
        }
        for(int i=0;i<n;i++)//display the product array
        {
           System.out.print(product.get(i)+"  "); 
        }
    }
}
5
10 3 5 6 2
180  600  360  300  900

სირთულის ანალიზი

დროის სირთულე

O (n) სადაც n არის მასივში არსებული ელემენტების რაოდენობა. აქ ჩვენ მხოლოდ 3-ჯერ გავდივართ და ვპოულობთ პროდუქტის მასივს.

სივრცის სირთულე

O (n) რადგან ჩვენ ვიყენებთ მარცხენა და მარჯვენა მასალებს ელემენტების პროდუქტების შესანახად.

ლიტერატურა