Cho một mảng số nguyên dương(arr[0-n] > 0) arr có n phần tử. Viết chương trình tìm tích nhỏ nhất của 2 số trong mảng. (n > 2)
Ví dụ:
Input: arr[] = {3, 4, 9, 6, 2, 4}
Output: 6 = 3 * 2
Cách 1: sử dụng vòng lặp
Sử dụng 2 vòng lặp để tìm tất cả các tích của một số với các số còn lại trong mảng và so sánh để tìm ra 2 phần tử có tích nhỏ nhất.
public class Main {
public static int findMinMulti(int[] arr, int n) {
int min = Integer.MAX_VALUE;
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
if (arr[i] * arr[j] < min)
min = arr[i] * arr[j];
}
}
return min;
}
public static void main(String[] args) {
int[] arr = {3, 4, 9, 6, 2, 4};
System.out.println(findMinMulti(arr, arr.length));
System.out.println(findMinMultiSort(arr, arr.length));
}
}
Output: 6
Độ phức tạp: O(n^2)
Cách 2: Sắp xếp
Sau khi sắp xếp mảng tăng dần, chúng ta chỉ cần nhân phần tử tại vị trí 0 và 1 để có kết quả vì 2 phần tử này là nhỏ nhất trong mảng
import java.util.Arrays;
public class Main {
public static int findMinMultiSort(int[] arr, int n) {
Arrays.sort(arr, 0, n);
return arr[0] * arr[1];
}
public static void main(String[] args) {
int[] arr = {3, 4, 9, 6, 2, 4};
System.out.println(findMinMulti(arr, arr.length));
System.out.println(findMinMultiSort(arr, arr.length));
}
}
Output: 6
Độ phức tạp: O(nlogn)
Link đề bài: https://www.geeksforgeeks.org/minimum-product-pair-an-array-of-positive-integers/