لغز صفيف المنتج


مستوى الصعوبة متوسط
كثيرا ما يطلب في Accolite أدوبي أمازون أجهزة آبل أسانا بلاك روك بلومبرغ ByteDance قلعة دي شو يباي إيفرنوت اكسبيديا Facebook جولدمان ساكس جوجل Houzz إنتل لينكد إن: lyft Microsoft مورجان ستانلي Nutanix العمل أوراكل Paypal Paytm Qualtrics ساليسفورسي SAP الخدمة الآن Snapchat Splunk التابلوه لوحة حية تويتر اوبر تأشيرة في إم وير مختبرات وول مارت ياهو ياندكس
مجموعة جروبون LeetCode

المشكلة بيان

في المنتج مجموعة مشكلة اللغز نحتاج إلى بناء مصفوفة حيث ith سيكون العنصر هو نتاج جميع العناصر في المصفوفة المحددة باستثناء العنصر في ith .

مثال

إدخال 

5

10 3 5 6 2

الناتج

180 600 360 300 900

خوارزمية لحل لغز مصفوفة المنتج

خطوة 1: خذ منتجًا متجهًا لتخزين المنتجات.
أ) قم بتهيئته بواسطة منتج المتجه

خطوة 2: أنشئ صفيفين يسارًا [] ويمينًا [] ، ويخزن على اليسار منتج العناصر حتى يسار فهرس ith في المصفوفة. الحق يخزن المنتج من العناصر حق الفهرس.

أ. قم بتهيئة العنصر الأول لليسار كـ 1 والعنصر الأخير من اليمين كـ 1.
ب. من اليسار ، قم بتحديث عناصر i من المصفوفة اليسرى بمنتج العنصر i-1 من المصفوفة المعطاة بالعنصر السابق من المصفوفة اليسرى. (يسار [i] = يسار [i-1] * صفيف [i-1]). من خلال القيام بذلك ، يخزن المنتج حتى الفهرس السابق في المصفوفة اليسرى من المصفوفة المحددة.
ج. من اليمين ، قم بتحديث عناصر i من المصفوفة اليمنى بمنتج العنصر i + 1 من المصفوفة المحددة بالعنصر التالي من المصفوفة الصحيحة. (يمين [i] = يمين [i + 1] * صفيف [i + 1]). من خلال القيام بذلك ، يخزن المنتج حتى الفهرس السابق في المصفوفة اليسرى من المصفوفة المحددة.

خطوة 3:  سيكون المنتج باستثناء العنصر الحالي هو نفسه منتج عناصر المصفوفات اليمنى واليسرى.
أ) ستكون مصفوفة المنتج ، المنتج [i] = يسار [i] * يمين [i].

شرح لحل لغز مصفوفة منتج

أولاً ، اجتياز المصفوفة من البداية وتخزين حاصل ضرب جميع العناصر السابقة لكل i. الآن قم باجتياز المصفوفة من الخلف وقم بتخزين المجموع من النهاية وقم بتخزين حاصل ضرب جميع العناصر بعد هذا العنصر.

اليسار [] = {10، 30، 150، 900، 1800}

صحيح [] = {1800 ، 180 ، 60 ، 12 ، 2}

الآن باستخدام هذه المصفوفة ، ابحث عن حاصل ضرب جميع العناصر في المصفوفة المحددة باستثناء العنصر في ith .

المنتج [] = {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 هو عدد العناصر الموجودة في المصفوفة. هنا ننتقل 3 مرات فقط ونجد مصفوفة المنتج.

تعقيد الفضاء

O (ن) لأننا نستخدم المصفوفات اليمنى واليسرى لتخزين منتجات العناصر.

مراجع