資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中醜數子陣列的最大長度
問題陳述
給定一個包含 N 個元素的陣列 arr[]（0 ≤ arr[i] ≤ 1000）。任務是找到僅包含醜數的子陣列的最大長度。
醜數是指其唯一質因數為 2、3 或 5 的數。
例如，以下是該序列中的一些數字：1、2、3、4、5、6、8、9、10、12、15……
示例
如果輸入陣列為 {1, 2, 7, 9, 120, 810, 374}，則答案為 3，因為：
最長的醜數子陣列是 {9, 120, 810}
演算法
- 建立一個無序集合，並將所有小於 1000 的醜數插入到集合中。
- 使用兩個名為 current_max 和 max_so_far 的變數遍歷陣列。
- 檢查每個元素是否在集合中。
- 如果找到一個醜數，則遞增 current_max 並將其與 max_so_far 進行比較。
- 如果 current_max > max_so_far，則 max_so_far = current_max。
- 每當找到一個非醜數元素時，將 current_max 重置為 0。
示例
#include <bits/stdc++.h>
using namespace std;
unsigned getUglyNumbers(int n) {
int ugly[n];
int i2 = 0, i3 = 0, i5 = 0;
int next_multiple_of_2 = 2;
int next_multiple_of_3 = 3;
int next_multiple_of_5 = 5;
int next_ugly_no = 1;
ugly[0] = 1;
for (int i = 1; i < n; i++) {
next_ugly_no = min(next_multiple_of_2, min(next_multiple_of_3, next_multiple_of_5));
ugly[i] = next_ugly_no;
if (next_ugly_no == next_multiple_of_2) {
i2 = i2 + 1;
next_multiple_of_2 = ugly[i2] * 2;
}
if (next_ugly_no == next_multiple_of_3) {
i3 = i3 + 1;
next_multiple_of_3 = ugly[i3] * 3;
}
if (next_ugly_no == next_multiple_of_5) {
i5 = i5 + 1;
next_multiple_of_5 = ugly[i5] * 5;
}
}
return next_ugly_no;
}
int maxUglySubarray(int arr[], int n) {
unordered_set<int> s;
int i = 1;
while (1) {
int next_ugly_number = getUglyNumbers(i);
if (next_ugly_number > 1000)
break;
s.insert(next_ugly_number);
i++;
}
int current_max = 0, max_so_far = 0;
for (int i = 0; i < n; i++) {
if (s.find(arr[i]) == s.end())
current_max = 0;
else {
current_max++;
max_so_far = max(current_max,
max_so_far);
}
}
return max_so_far;
}
int main() {
int arr[] = {1, 2, 7, 9, 120, 810, 374};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sub-array size of consecutive ugly numbers = " << maxUglySubarray(arr, n) << endl;
return 0;
}輸出
編譯並執行以上程式時，會生成以下輸出：
Maximum sub-array size of consecutive ugly numbers = 3
更新於：2020年1月10日
72 次檢視
廣告