資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究C++ 中的產品陣列難題 (O(1) 空間)
接下來我們將看到一個有趣的問題，與陣列有關。有一個數組，其中有 n 個元素。我們必須建立一個包含 n 個元素的另一個數組。但是在第二個陣列的第 i 個位置，將儲存第一個陣列中除了第 i 個元素之外的所有元素的乘積。此問題的限制條件是，我們不能使用除法運算子。我們必須不使用任何其他空間直接解決此問題。
如果我們可以使用除法運算，可以透過獲取所有元素的乘積，然後除以第一個陣列的第 i 個元素，並將其儲存在第二個陣列的第 i 個位置來輕鬆解決此問題。
這裡，我們透過取一個臨時變數來解決，即找出左右部分的乘積。該值將放入最終陣列中。因此，它不會佔用額外的空間。
演算法
productArray(arr, n)
begin define an array called res of size n fill the res array with 1 temp := 1 for i in range 1 to n, do res[i] := temp; temp := temp * arr[i] done for i in range n-1 down to 0, do res[i] = res[i] * temp temp := temp * arr[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) {
int temp = 1;
for(int i = 0; i<n; i++) {
product[i] = 1; //set all elements of product as 1
}
for(int i = 0; i < n; i++) { //temp variable will hold product of elements on left excluding arr[i]
product[i] = temp;
temp *= arr[i];
}
temp = 1;
for(int i = n - 1; i >= 0; i--) { //temp variable will hold product of elements on right excluding arr[i]
product[i] *= temp;
temp *= arr[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
更新於：2019 年 7 月 30 日
102 人次觀看
廣告