Дан массив неотрицательных целых чисел. Найдите наибольшее кратное 3, которое можно сформировать из элементов массива.
Например, если входной массив равен {8, 1, 9}, выходной сигнал должен быть «9 8 1», а если входной массив равен {8, 1, 7, 6, 0}, выходной сигнал должен быть «8 7». 6 0 ”.
Метод 1 (грубая сила)
Простой и прямой подход заключается в создании всех комбинаций элементов и отслеживании наибольшего числа, которое делится на 3.
Сложность времени: O (nx 2 ^ n). Будет 2 ^ n комбинаций элементов массива. Для сравнения каждой комбинации с наибольшим числом пока может потребоваться O (n) времени.
Вспомогательный пробел: O (n) // во избежание переполнения целого числа предполагается, что наибольшее число хранится в виде массива.
Метод 2 (хитрый)
Эта проблема может быть эффективно решена с помощью O (n) дополнительного пространства. Этот метод основан на следующих фактах о числах, кратных 3.
1) Число кратно 3, если и только если сумма цифр числа кратна 3. Например, давайте рассмотрим 8760, это кратно 3, потому что сумма цифр равна 8 + 7+ 6+ 0 = 21, который кратен 3.
2) Если число кратно 3, то все его перестановки также кратны 3. Например, так как 6078 кратно 3, числа 8760, 7608, 7068,… .. также кратны 3.
3) Мы получаем тот же остаток, когда делим число и сумму цифр числа. Например, если разделить число 151 и сумму его цифр 7 на 3, мы получим такой же остаток 1.
Какова идея вышеупомянутых фактов?
Значение 10% 3 и 100% 3 равно 1. То же самое верно для всех высших степеней 10, потому что 3 делит 9, 99, 999 и т. Д.
Давайте рассмотрим трехзначное число n, чтобы доказать вышеуказанные факты. Пусть первая, вторая и третья цифры n будут «a», «b» и «c» соответственно. п можно записать как
n = 100.a + 10.b + c
Поскольку (10 ^ x)% 3 равно 1 для любого x, вышеприведенное выражение дает тот же остаток, что и следующее выражение
1.a + 1.b + c
Таким образом, остаток, полученный суммой цифр и 'n', одинаков.
Ниже приведено решение, основанное на приведенном выше наблюдении.
1. Сортировать массив в порядке убывания.
2. Возьмите три очереди. Один для хранения элементов, который при делении на 3 дает остаток как 0. Вторая очередь хранит цифры, которые при делении на 3 дают остаток как 1. Третья очередь хранит цифры, которые при делении на 3 дают остаток как 2. Вызовите их как очередь0, очередь1 и очередь2
3. Найдите сумму всех цифр.
4. Возникают три случая:
…… 4.1 . Сумма цифр делится на 3. Удалить все цифры из трех очередей. Сортируйте их по возрастанию. Выведите массив.
…… 4.2 Сумма цифр дает остаток 1 при делении на 3.
Удалить один элемент из очереди1. Если очередь1 пуста, удалите два элемента из очереди2. Если очередь2 содержит менее двух элементов, это число невозможно.
…… 4.3 Сумма цифр дает остаток 2 при делении на 3.
Удалить один элемент из очереди2. Если очередь2 пуста, удалите два элемента из очереди1. Если очередь1 содержит менее двух элементов, это число невозможно.
5. Наконец, опустошите все очереди во вспомогательный массив. Сортировать вспомогательный массив в порядке возрастания. Выведите вспомогательный массив.
Приведенный ниже код работает, только если входные массивы имеют числа от 0 до 9. Он может быть легко расширен для любого массива натуральных чисел. Нам просто нужно изменить часть, где мы сортируем массив в порядке убывания, в конце кода.
C ++
#include <bits/stdc++.h>
using namespace std;
void populateAux(int aux[], queue<int> queue0, queue<int> queue1,
queue<int> queue2, int* top)
{
while (!queue0.empty()) {
aux[(*top)++] = queue0.front();
queue0.pop();
}
while (!queue1.empty()) {
aux[(*top)++] = queue1.front();
queue1.pop();
}
while (!queue2.empty()) {
aux[(*top)++] = queue2.front();
queue2.pop();
}
}
int findMaxMultupleOf3(int arr[], int size)
{
sort(arr, arr + size);
queue<int> queue0, queue1, queue2;
int i, sum;
for (i = 0, sum = 0; i < size; ++i) {
sum += arr[i];
if ((arr[i] % 3) == 0)
queue0.push(arr[i]);
else if ((arr[i] % 3) == 1)
queue1.push(arr[i]);
else
queue2.push(arr[i]);
}
if ((sum % 3) == 1) {
if (!queue1.empty())
queue1.pop();
else {
if (!queue2.empty())
queue2.pop();
else
return 0;
if (!queue2.empty())
queue2.pop();
else
return 0;
}
}
else if ((sum % 3) == 2) {
if (!queue2.empty())
queue2.pop();
else {
if (!queue1.empty())
queue1.pop();
else
return 0;
if (!queue1.empty())
queue1.pop();
else
return 0;
}
}
int aux[size], top = 0;
populateAux(aux, queue0, queue1, queue2, &top);
sort(aux, aux + top, greater<int>());
for (int i = 0; i < top; ++i)
cout << aux[i] << " ";
return top;
}
int main()
{
int arr[] = { 8, 1, 7, 6, 0 };
int size = sizeof(arr) / sizeof(arr[0]);
if (findMaxMultupleOf3(arr, size) == 0)
cout << "Not Possible";
return 0;
}
|
С
#include <stdio.h>
#include <stdlib.h>
typedef struct Queue {
int front;
int rear;
int capacity;
int* array;
} Queue;
Queue* createQueue(int capacity)
{
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->capacity = capacity;
queue->front = queue->rear = -1;
queue->array = (int*)malloc(queue->capacity * sizeof(int));
return queue;
}
int isEmpty(Queue* queue)
{
return queue->front == -1;
}
void Enqueue(Queue* queue, int item)
{
queue->array[++queue->rear] = item;
if (isEmpty(queue))
++queue->front;
}
int Dequeue(Queue* queue)
{
int item = queue->array[queue->front];
if (queue->front == queue->rear)
queue->front = queue->rear = -1;
else
queue->front++;
return item;
}
void printArr(int* arr, int size)
{
int i;
for (i = 0; i < size; ++i)
printf("%d ", arr[i]);
}
int compareAsc(const void* a, const void* b)
{
return *(int*)a > *(int*)b;
}
int compareDesc(const void* a, const void* b)
{
return *(int*)a < *(int*)b;
}
void populateAux(int* aux, Queue* queue0, Queue* queue1,
Queue* queue2, int* top)
{
while (!isEmpty(queue0))
aux[(*top)++] = Dequeue(queue0);
while (!isEmpty(queue1))
aux[(*top)++] = Dequeue(queue1);
while (!isEmpty(queue2))
aux[(*top)++] = Dequeue(queue2);
}
int findMaxMultupleOf3(int* arr, int size)
{
qsort(arr, size, sizeof(int), compareAsc);
Queue* queue0 = createQueue(size);
Queue* queue1 = createQueue(size);
Queue* queue2 = createQueue(size);
int i, sum;
for (i = 0, sum = 0; i < size; ++i) {
sum += arr[i];
if ((arr[i] % 3) == 0)
Enqueue(queue0, arr[i]);
else if ((arr[i] % 3) == 1)
Enqueue(queue1, arr[i]);
else
Enqueue(queue2, arr[i]);
}
if ((sum % 3) == 1) {
if (!isEmpty(queue1))
Dequeue(queue1);
else {
if (!isEmpty(queue2))
Dequeue(queue2);
else
return 0;
if (!isEmpty(queue2))
Dequeue(queue2);
else
return 0;
}
}
else if ((sum % 3) == 2) {
if (!isEmpty(queue2))
Dequeue(queue2);
else {
if (!isEmpty(queue1))
Dequeue(queue1);
else
return 0;
if (!isEmpty(queue1))
Dequeue(queue1);
else
return 0;
}
}
int aux[size], top = 0;
populateAux(aux, queue0, queue1, queue2, &top);
qsort(aux, top, sizeof(int), compareDesc);
printArr(aux, top);
return top;
}
int main()
{
int arr[] = { 8, 1, 7, 6, 0 };
int size = sizeof(arr) / sizeof(arr[0]);
if (findMaxMultupleOf3(arr, size) == 0)
printf("Not Possible");
return 0;
}
|
Джава
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Collections;
public class Geeks {
public static int populateAux(int aux[], Queue<Integer> queue0,
Queue<Integer> queue1, Queue<Integer> queue2)
{
int top=0;
while(!queue0.isEmpty())
{
aux[top++]=queue0.remove();
}
while(!queue1.isEmpty())
{
aux[top++]=queue1.remove();
}
while(!queue2.isEmpty())
{
aux[top++]=queue2.remove();
}
return top;
}
public static boolean findMaxMultupleOf3(int arr[])
{
Arrays.sort(arr);
Queue<Integer> queue0=new LinkedList<>();
Queue<Integer> queue1=new LinkedList<>();
Queue<Integer> queue2=new LinkedList<>();
int sum=0;
for (int i = 0; i < arr.length; ++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 % 3) == 1)
{
if (!queue1.isEmpty())
queue1.remove();
else
{
if (!queue2.isEmpty())
queue2.remove();
else
return false;
if (!queue2.isEmpty())
queue2.remove();
else
return false;
}
}
else if ((sum % 3) == 2)
{
if (!queue2.isEmpty())
queue2.remove();
else
{
if (!queue1.isEmpty())
queue1.remove();
else
return false;
if (!queue1.isEmpty())
queue1.remove();
else
return false;
}
}
int aux[]=new int[arr.length];
int top=populateAux(aux,queue0,queue1,queue2);
Arrays.sort(aux,0,top);
for (int i = top-1; i>=0; i--)
System.out.print(aux[i]+" ") ;
return true;
}
public static void main(String args[])
{
int arr[] = { 8, 1, 7, 6, 0 };
if (!findMaxMultupleOf3(arr))
System.out.println("Not possible") ;
}
}
|
C #
using System;
using System.Collections.Generic;
class Geeks
{
public static int populateAux(int []aux, Queue<int> queue0,
Queue<int> queue1, Queue<int> queue2)
{
int top = 0;
while(queue0.Count != 0)
{
aux[top++] = queue0.Dequeue();
}
while(queue1.Count != 0)
{
aux[top++] = queue1.Dequeue();
}
while(queue2.Count != 0)
{
aux[top++] = queue2.Dequeue();
}
return top;
}
public static bool findMaxMultupleOf3(int []arr)
{
Array.Sort(arr);
Queue<int> queue0 = new Queue<int>();
Queue<int> queue1 = new Queue<int>();
Queue<int> queue2 = new Queue<int>();
int sum=0;
for (int i = 0; i < arr.Length; ++i)
{
sum += arr[i];
if ((arr[i] % 3) == 0)
queue0.Enqueue(arr[i]);
else if ((arr[i] % 3) == 1)
queue1.Enqueue(arr[i]);
else
queue2.Enqueue(arr[i]);
}
if ((sum % 3) == 1)
{
if (queue1.Count != 0)
queue1.Dequeue();
else
{
if (queue2.Count != 0)
queue2.Dequeue();
else
return false;
if (queue2.Count != 0)
queue2.Dequeue();
else
return false;
}
}
else if ((sum % 3) == 2)
{
if (queue2.Count != 0)
queue2.Dequeue();
else
{
if (queue1.Count != 0)
queue1.Dequeue();
else
return false;
if (queue1.Count != 0)
queue1.Dequeue();
else
return false;
}
}
int []aux = new int[arr.Length];
int top = populateAux(aux,queue0,queue1,queue2);
Array.Sort(aux,0,top);
for (int i = top-1; i >= 0; i--)
Console.Write(aux[i]+" ") ;
return true;
}
public static void Main()
{
int []arr = { 8, 1, 7, 6, 0 };
if (!findMaxMultupleOf3(arr))
Console.WriteLine("Not possible") ;
}
}
|
Выход:
8 7 6 0
Вышеуказанный способ может быть оптимизирован следующими способами.
1) Мы можем использовать сортировку кучи или сортировку слиянием, чтобы сделать временную сложность O (nLogn).
2) Мы можем избежать лишнего места для очередей. Мы знаем, что максимум два элемента будут удалены из входного массива. Таким образом, мы можем отслеживать два элемента в двух переменных.
3) В конце, вместо сортировки массива снова в порядке убывания, мы можем напечатать отсортированный по возрастанию массив в обратном порядке. При печати в обратном порядке, мы можем пропустить два элемента, которые будут удалены.
Сложность времени: O (nLogn), предполагая, что алгоритм O (nLogn) используется для сортировки.
Найти наибольшее кратное 3 | Установите 2 (В O (n) время и O (1) пространство)
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
Найти наибольшее кратное 3 | Установите 1 (используя очередь)
0.00 (0%) 0 votes