차례
문제 정책
"3의 가장 큰 배수 찾기"문제는 정렬 긍정적 인 정수(0-9). 배열의 요소를 재정렬하여 형성 할 수있는 최대 3의 배수를 찾으십시오.
예
arr[] = {5, 2, 1, 0, 9, 3}
9 5 3 1 0
arr[] = {1, 2, 3, 4, 5}
5 4 3 2 1
3의 가장 큰 배수를 찾는 알고리즘
3의 배수마다 특별한 속성이 있습니다. 숫자의 합계도 XNUMX으로 나눌 수 있습니다. 예를 들어
123은 3으로 나눌 수 있으므로 (1 + 2 + 3) = 6도 3으로 나눌 수 있습니다. 따라서이 속성을 사용하여 위의 문제를 해결할 수 있습니다.
종류 배열을 오름차순으로 유지하고 꼬리, queue0은 0으로 나눌 때 나머지 3을 남기는 배열의 모든 요소를 저장하고, queue1은 1으로 나눌 때 나머지 3을 남기는 배열의 모든 요소를 저장하고 queue2는 나머지 2를 남겨 두는 배열의 요소를 저장합니다. 3으로 나눕니다.
배열의 모든 요소의 합에 따르면 3 가지 경우가 있습니다.
사례 : 3으로 나눌 수 있음
세 큐의 모든 요소를 배열에 저장하고 배열을 내림차순으로 정렬합니다. 이것이 답입니다.
사례 : 1으로 나누면 나머지 3을 남깁니다.
queue1에서 요소 1 개를 제거하거나 queue1이 비어있는 경우 queue2에서 요소 2 개를 제거합니다. 이러한 작업을 수행 할 수없는 경우 3의 배수를 형성 할 방법이 없습니다.
대기열에 남아있는 모든 요소를 배열로 이동하고 배열을 내림차순으로 정렬합니다. 이것이 답입니다.
사례 : 2으로 나누면 나머지 3을 남깁니다.
queue1에서 요소 2 개를 제거하거나 queue2가 비어있는 경우 queue2에서 요소 1 개를 제거합니다. 또는 이러한 작업을 수행 할 수없는 경우 3 인 경우 여러 요소에서 이동할 방법이 없습니다.
대기열에 남아있는 모든 요소를 배열로 이동하고 배열을 내림차순으로 정렬합니다. 이것이 답입니다.
암호
3의 가장 큰 배수를 찾는 자바 코드
import java.util.*;
class FindTheLargestMultipleOf3 {
private static void fillAns(ArrayList<Integer> ans, Queue<Integer> q0, Queue<Integer> q1, Queue<Integer> q2) {
while (!q0.isEmpty()) {
ans.add(q0.poll());
}
while (!q1.isEmpty()) {
ans.add(q1.poll());
}
while (!q2.isEmpty()) {
ans.add(q2.poll());
}
}
private static boolean findLargestMultiple(int[] arr) {
int n = arr.length;
// sort the array in ascending order
Arrays.sort(arr);
// maintain 3 queues as mentioned
Queue<Integer> queue0 = new LinkedList<>();
Queue<Integer> queue1 = new LinkedList<>();
Queue<Integer> queue2 = new LinkedList<>();
// variable to store the sum of all the elements in array
int sum = 0;
// traverse the array and add elements to queue
// also find the sum
for (int i = 0; i < n; i++) {
sum += arr[i];
if (arr[i] % 3 == 0) {
queue0.add(arr[i]);
} else if (arr[i] % 3 == 1) {
queue1.add((arr[i]));
} else {
queue2.add(arr[i]);
}
}
// if sum is divisible by 3, do nothing
if (sum % 3 == 0) {
}
// if sum leaves remainder 1 when divided by 3
else if (sum % 3 == 1) {
// remove 1 element from queue1
if (!queue1.isEmpty()) {
queue1.remove();
} else {
// or remove two elements from queue2
if (!queue2.isEmpty()) {
queue2.remove();
} else {
return false;
}
if (!queue2.isEmpty()) {
queue2.remove();
} else {
return false;
}
}
}
// if sum leaves remainder 2 when divided by 3
else {
// remove one element from queue2
if (!queue2.isEmpty()) {
queue2.remove();
} else {
// or remove 2 elements from queue1
if (!queue1.isEmpty()) {
queue1.remove();
} else {
return false;
}
if (!queue1.isEmpty()) {
queue1.remove();
} else {
return false;
}
}
}
// add the remaining elements to a list
ArrayList<Integer> ans = new ArrayList<>();
fillAns(ans, queue0, queue1, queue2);
// sort the list in descending order, this is the answer
Collections.sort(ans, Collections.reverseOrder());
for (int i = 0; i < ans.size(); i++) {
System.out.print(ans.get(i) + " ");
}
System.out.println();
return true;
}
public static void main(String[] args) {
// Example 1
int arr1[] = new int[]{5, 2, 1, 0, 9, 3};
if (!findLargestMultiple(arr1)) {
System.out.println("Not Possible");
}
// Example 2
int arr2[] = new int[]{1, 2, 3, 4, 5};
if (!findLargestMultiple(arr2)) {
System.out.println("Not Possible");
}
}
}
9 5 3 1 0 5 4 3 2 1
3의 가장 큰 배수를 찾는 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
void fillAns(vector<int> &ans, queue<int> q0, queue<int> q1, queue<int> q2) {
while (!q0.empty()) {
ans.push_back(q0.front());
q0.pop();
}
while (!q1.empty()) {
ans.push_back(q1.front());
q1.pop();
}
while (!q2.empty()) {
ans.push_back(q2.front());
q2.pop();
}
}
bool findLargestMultiple(int *arr, int n) {
// sort the array in ascending order
sort(arr, arr + n);
// maintain 3 queues as mentioned
queue<int> q0;
queue<int> q1;
queue<int> q2;
// variable to store the sum of all the elements in array
int sum = 0;
// traverse the array and add elements to queue
// also find the sum
for (int i = 0; i < n; i++) {
sum += arr[i];
if (arr[i] % 3 == 0) {
q0.push(arr[i]);
} else if (arr[i] % 3 == 1) {
q1.push(arr[i]);
} else {
q2.push(arr[i]);
}
}
// if sum is divisible by 3, do nothing
if (sum % 3 == 0) {
}
// if sum leaves remainder 1 when divided by 3
else if (sum % 3 == 1) {
// remove 1 element from queue1
if (!q1.empty()) {
q1.pop();
} else {
// or remove two elements from queue2
if (!q2.empty()) {
q2.pop();
} else {
return false;
}
if (!q2.empty()) {
q2.pop();
} else {
return false;
}
}
}
// if sum leaves remainder 2 when divided by 3
else {
// remove one element from queue2
if (!q2.empty()) {
q2.pop();
} else {
// or remove 2 elements from queue1
if (!q1.empty()) {
q1.pop();
} else {
return false;
}
if (!q1.empty()) {
q1.pop();
} else {
return false;
}
}
}
// add the remaining elements to a list
vector<int> ans;
fillAns(ans, q0, q1, q2);
// sort the list in descending order, this is the answer
sort(ans.begin(), ans.end(), greater<int>());
for (int i = 0; i < ans.size(); i++) {
cout<<ans[i]<<" ";
}
cout<<endl;
return true;
}
int main() {
// Example 1
int arr1[] = {5, 2, 1, 0, 9, 3};
if (!findLargestMultiple(arr1,sizeof(arr1) / sizeof(arr1[0]))) {
cout<<"Not Possible"<<endl;
}
// Example 2
int arr2[] = {1, 2, 3, 4, 5};
if (!findLargestMultiple(arr2,sizeof(arr2) / sizeof(arr2[0]))) {
cout<<"Not Possible"<<endl;
}
return 0;
}
9 5 3 1 0 5 4 3 2 1
복잡성 분석
시간 복잡성
O (N log N), 세 개의 중간 대기열을 정렬했기 때문입니다. 그리고 최악의 경우 모든 n 요소가 단일 대기열로 끝날 수 있습니다. 그러면 최악의 복잡성은 O (N log N)입니다.
공간 복잡성
의 위에), N 개의 요소를 저장하기 위해 큐를 사용했기 때문입니다. 알고리즘에는 선형 공간 복잡성이 있습니다.
