找到最小的數 M，將其除以輸入陣列中的 n-1 個數。如果沒有這樣的 M 則回傳 -1。
例子：
array = [2,3,5]
回答 ：
6
解釋 ：
6 can be divided by 2 and 3
例子：
array = [2,3,6]
回答：
-1
解釋 ：
It's not possible in this case so return -1.
我的代碼：
由于我們需要找到最小的M，我只選擇從 0 到 n-2 的元素
public int process(int[] arr) {
int answer = 1;
for(int i=0; i<arr.length-1; i ) {
answer *= arr[i];
}
return answer;
}
該程式適用于這 2 個示例測驗用例，但對于多個隱藏的測驗用例卻失敗了。我試圖了解我在這里缺少什么。
uj5u.com熱心網友回復：
最小公倍數 (LCM) 的計算
任務中的一個問題是計算 2 個數字的最小公倍數。該方法public int lowerCommonMultiple(int x1, int x2)解決了這個問題，我認為它可以在其他情況下使用。
類方法串列
所有代碼都包含在BestMultiple類的方法中。這些方法（不包括main）是：
public int[] removeElem(int[] tensArray, int rm_index): 用于從陣列中洗掉一個元素public int leastCommonMultiple(int x1, int x2): 計??算 2 個數的最小公倍數private int getLeastCommonMultipleNnumber(int[] arr)：計算陣列中包含的 N-1 個整數的最小公倍數public int process(int[] arr)：計算 N 個整數陣列的 N-1 個數的最小倍數；它管理許多測驗奇怪的情況（陣列為空、elem<=0 等）
可能是代碼沒有優化，但我希望它是正確的（添加的輸出表明它可以正常作業，至少在選擇的測驗用例的情況下）。
public class BestMultiple {
/*
Method: removeElem() remove an element from
an array.
*/
public int[] removeElem(int[] tensArray, int rm_index) {
// Create a proxy array of size one less than original array
int[] proxyArray = new int[tensArray.length - 1];
// copy all the elements in the original to proxy array
// except the one at index
for (int i = 0, k = 0; i < tensArray.length; i ) {
// check if index is crossed, continue without copying
if (i == rm_index) {
continue;
}
// else copy the element
proxyArray[k ] = tensArray[i];
}
return proxyArray;
}
/*
Method: leastCommonMultiple() Calculates the Least Common
multiple for 2 numbers
*/
public int leastCommonMultiple(int x1, int x2) {
int lcm = 1;
int max = x1;
if ((x1 == 0) || (x2 == 0)) {
lcm = 0;
} else {
if (x2 > x1) {
max = x2;
}
for (int i = 2; i <= max; i ) {
int exp_x1 = 0;
int exp_x2 = 0;
int exp = 0;
if (x1 > 1) {
while ((x1 % i) == 0) {
exp_x1 ;
x1 /= i;
}
}
if (x2 > 1) {
while ((x2 % i) == 0) {
exp_x2 ;
x2 /= i;
}
}
if ((exp_x1 > 0) || (exp_x2 > 0)) {
exp = exp_x1;
if (exp_x2 > exp) {
exp = exp_x2;
}
while (exp > 0) {
lcm *= i;
exp--;
}
}
}
}
return lcm;
}
/*
Method: getLeastCommonMultipleNnumber()
Calculates the least common multiple of N-1
integer contain in an array
*/
public int getLeastCommonMultipleNnumber(int[] arr) {
int multiple = 1;
if (arr.length >= 2) {
multiple = leastCommonMultiple(arr[0], arr[1]);
for (int j = 2; j < arr.length; j ) {
multiple = leastCommonMultiple(multiple, arr[j]);
}
} else {
// array with only 2 elements
multiple = arr[0];
}
return multiple;
}
/*
Method: process()
Calculates the least multiple of EXACTLY N-1
number of an array of N integer
*/
public int process(int[] arr) {
int answer;
if (arr.length <= 1) {
// array contains only one element or is empty => return -1
answer = -1;
} else {
int pos_elem_zero = -1;
int prod = 1;
for (int i = 0; i < arr.length; i ) {
if (arr[i] > 0) {
prod *= arr[i];
} else {
if (arr[i] < 0) {
// integer < 0 are not allowed
return -1;
}
if (pos_elem_zero == -1) {
pos_elem_zero = i;
} else {
// there are more element == 0
return -1;
}
}
}
if (pos_elem_zero >= 0) {
// there is one element == 0
arr = this.removeElem(arr, pos_elem_zero);
return getLeastCommonMultipleNnumber(arr);
}
// managing of normal test case
answer = prod;
for (int i = 0; i < arr.length; i ) {
int elem = arr[i];
int[] arr2 = this.removeElem(arr, i);
int multiple = getLeastCommonMultipleNnumber(arr2);
if (multiple > elem) {
if ((multiple % elem) != 0) {
if (multiple < answer) {
answer = multiple;
}
}
} else {
if (multiple < elem) {
answer = multiple;
}
}
}
if (answer == prod) {
answer = -1;
}
}
return answer;
}
/*
Method: main() Executes test of process()
method
*/
public static void main(String[] args) {
BestMultiple bm = new BestMultiple();
int[] arr1 = {6,30,5,3};
int[] arr2 = {1,2,3};
int[] arr3 = {1,2,3,3};
int[] arr4 = {6,7,5,3};
int[] arr5 = {9,14, 21};
int[] arr6 = {2,4};
int[] arr7 = {2,3,5};
int[] arr8 = {2,3,6};
int[] arr9 = {2};
int[] arr10 = {};
int[] arr11 = {2,3,0};
int[] arr12 = {0,2,3,0};
int[] arr13 = {20,3};
int[] arr14 = {0,6,15};
int[] arr15 = {1,6,15,-1};
int[] arr16 = {1,6,15};
int[] arr17 = {2,3,0,6,15};
System.out.println("{6,30,5,3} --> " bm.process(arr1));
System.out.println("{1,2,3} --> " bm.process(arr2));
System.out.println("{1,2,3,3} --> " bm.process(arr3));
System.out.println("{6,7,5,3} --> " bm.process(arr4));
System.out.println("{9,14,21} --> " bm.process(arr5));
System.out.println("{2,4} --> " bm.process(arr6));
System.out.println("{2,3,5} --> " bm.process(arr7));
System.out.println("{2,3,6} --> " bm.process(arr8));
System.out.println("{2} --> " bm.process(arr9));
System.out.println("{} --> " bm.process(arr10));
System.out.println("{2,3,0} --> " bm.process(arr11));
System.out.println("{0,2,3,0} --> " bm.process(arr12));
System.out.println("{20,3} --> " bm.process(arr13));
System.out.println("{0,6,15} --> " bm.process(arr14));
System.out.println("{1,6,15,-1} --> " bm.process(arr15));
System.out.println("{1,6,15} --> " bm.process(arr16));
System.out.println("{2,3,0,6,15} --> " bm.process(arr17));
}
}
程式的輸出
選擇了測驗用例的程式的輸出是：
{6,30,5,3} --> -1
{1,2,3} --> 2
{1,2,3,3} --> 3
{6,7,5,3} --> 30
{9,14,21} --> 42
{2,4} --> 2
{2,3,5} --> 6
{2,3,6} --> -1
{2} --> -1
{} --> -1
{2,3,0} --> 6
{0,2,3,0} --> -1
{20,3} --> 3
{0,6,15} --> 30
{1,6,15,-1} --> -1
{1,6,15} --> 6
{2,3,0,6,15} --> 30
uj5u.com熱心網友回復：
您實作的方式process()假定輸入陣列已排序。但無論如何，我認為排序在這里沒有幫助。請注意，滿足給定條件的數字可以除以最大的數字。因為[2, 3, 5, 6]它是6。將所有元素的乘積除以從最大到最小的連續元素并在第一個不是除數的地方停止也是不正確的。在示例中，[2, 4, 5, 6]這將2 * 4 * 5 = 40在正確答案為 時給出20。
我的想法是使用受Eratosthenes 篩子啟發的演算法。注意滿足條件的數不能大于所有元素的乘積。因此，創建一個divisors[]索引從 0 到arraywhere元素的乘積的表，divisors[i]表示有多少來自arraydivide的元素i。遍歷元素array并遞增divisors[i]其中i除以元素的所有元素。然后找到第一個ifor which divisors[i] == n - 1。
限制是divisors可能很大，具體取決于產品是什么array，因此適用性將僅限于 中相對較小的值array。
uj5u.com熱心網友回復：
您首先撰寫一個方法，該方法process計算每個子陣列的最小數量，其中一個元素被排除在外：
public static int process(int... arr) {
int min = -1;
for (int i = 0; i < arr.length; i) {
int r = process(arr, i);
if (r != -1) {
if (min == -1) {
min = r;
} else {
min = Math.min(min, r);
}
}
}
return min;
}
第二種process方法如下所示：
private static int process(int[] arr, int exclude) {
int result = 0;
for (int i = 0; i < arr.length; i) {
if (i != exclude) {
if (result == 0) {
result = arr[i];
} else {
result = lcm(result, arr[i]);
}
}
}
if (result%arr[exclude] == 0) {
return -1;
}
return result;
}
您需要一種計算兩個數字的 LCM 的方法。在這里，我將使用第二種計算 GCD 的方法：
private static int lcm(int a, int b) {
return a*b/gcd(a,b);
}
private static int gcd(int a, int b) {
if (a == 0) {
return b;
} else if (b == 0) {
return a;
} else {
while (a != b) {
if (a > b) {
a -= b;
} else {
b -= a;
}
}
return a;
}
}
例子：
System.out.println(process(2, 3, 5)); // prints 6
System.out.println(process(2, 3, 6)); // prints -1
System.out.println(process(9, 14, 21)); // prints 42 (divisible by 14 and 21, but not by 9
System.out.println(process(6, 7, 5, 3)); // prints 30 (divisible by 6, 5, 3, but not by 7
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532372.html
標籤：爪哇算法