Найдите наибольшее кратное 3 из массива цифр в O (n) временной сложности
Дан массив цифр (от 0 до 9). Найдите наибольшее число, которое можно составить из некоторых или всех цифр массива и которое делится на 3. Один и тот же элемент может встречаться в массиве несколько раз, но каждый элемент массива может использоваться только один раз. Примеры: Ввод: обр[] = {5, 4, 3, 1, 1} Выход: 4311
Алгоритм
- Получите размер массива и ввод массива и вычислите сумму при получении ввода.
- Отсортировать массив в порядке возрастания
- Возьмите три очереди, переберите массив и разделите цифру на 3 и поместите в соответствующие очереди на основе остатка,
Queue0 для хранения цифры % 3 == 0
Queue1 для хранения цифры % 3 == 1
Queue2 для хранения цифры % 3 == 2 - Вычислить остаток = сумма % 3,
если остаток равен 1, удалить один элемент из Очереди1 или два удалить из Очереди2
иначе, если остаток равен 2 Удалить один элемент из Очереди2 или два удалить из Очереди1 - Объединить Queue0, Queue1 и Queue2 в одну очередь
- Сортировка очереди слияния в порядке убывания
- Печать объединенной очереди.
Код
#include<stdio.h>
int main()
{
int n,sum=0;
scanf("%d",&n);
int a[n],q1[n],q2[n],q3[n];
int c1=0,c2=0,c3=0;
for(int i=0;i<n;i++) {
scanf("%d",&a[i]);
sum+=a[i]; }
for(int i=0;i<n;i++){
if (a[i]%3==0) {
q1[c1]=a[i]; c1++; }
else if (a[i]%3==1) {
q2[c2]=a[i]; c2++; }
else {
q3[c3]=a[i]; c3++; }
}
if (sum%3==1&&c1!=0)
c1--;
else {
if (c2>1)
c2-2;
else
printf("Not Possible");
}
if (sum%3==2&&c2!=0)
c2--;
else {
if (q1>1)
c1-2;
else
printf("Not Possible");
}
int k=0,b[n];
for(int i=0;i<c1;i++) {
b[k]=q1[i]; k++; }
for(int i=0;i<c2;i++) {
b[k]=q2[i]; k++; }
for(int i=0;i<c3;i++) {
b[k]=q3[i]; k++; }
}
Я новичок в кодировании и не мог понять очередь сортировки и слияния за O (n). Нужна помощь с шагом 2 и 5.
Разве нам не нужно 2 цикла для гистограммы. Код должен быть в O(n) для (i = 0; i < 10; ++i) for(j = 0; j < inputValue; j++) if ( hist[j] == i) results[i]+ +;
@ Арджун Вы можете сделать это с помощью одного цикла. int h[10] = {0}; for (i=0; i<n; i++) h[a[i]]++; На самом деле, вы можете вычислить гистограмму, читая ввод. Вам даже не нужен массив a. Прочитайте каждую цифру, обновите сумму и обновите гистограмму.
На шаге 4 вы уменьшите количество одной или двух цифр в гистограмме. Затем для генерации вывода требуется два цикла: for (i=9; i>=0;i--) for (count=h[i]; count>0; count--) result[r++] = i; Но эти два цикла выполняются в общей сложности n раз, поскольку сумма отсчетов в гистограмме равна n.
Если хотите предложить то, что я считаю более быстрым подходом в целом. Не просто никаких очередей, а простое условие для определения делимости.
Ответы 2
Чтобы отсортировать по O(n), вам нужно использовать Radix sort.
// Let's start with the array that your code generates in step 5
int b[4] = {1, 1, 4, 3}
// Count the number of times each value is seen.
int buckets[10] = {};
for (int i=0; i<4; i++)
buckets[b[i]]++;
// Update the b array with the sorted data.
int *b_iterator = &b[0];
for (int i=0; i<10; i++)
for (int count=0; count<buckets[i]; count++)
*b_iterator++ = i;
// b is now sorted. {1, 1, 3, 4}.
Нет необходимости распаковывать то, что ищет OP. Гистограмма содержит всю необходимую информацию.
1. Отсортируйте массив в порядке возрастания (сортировка подсчетом).
2. Очередь q0 хранит элементы, которые при делении на 3 дают остаток 0.
3. Очередь q1 хранит элементы, которые при делении на 3 дают остаток 1.
4. Очередь q2 хранит элементы, которые при делении на 3 дают остаток 2.
5.Найди сумму всех заданных цифр. Пусть это будет s.
6. Если s делится на 3, перейдите к шагу 9.
7.Если s при делении на 3 дает остаток 1:
Удалите один элемент из q1.
Если q1 пуст, удалите два элемента из q2.
Если q2 содержит менее двух элементов, число невозможно.
8.Если s при делении на 3 дает остаток 2:
Удалите один элемент из q2.
Если q2 пуст, удалите два элемента из q1.
Если q1 содержит менее двух элементов, число невозможно.
9. Очистите все очереди во временный массив и отсортируйте его в порядке убывания.
#include<stdio.h>
int main()
{
int n,max,f=0,c=0;
scanf("%d",&n);
int a[n],ct[10] = {0},b[10],sum=0;
for(int i=0;i<n;i++) {
scanf("%d",&a[i]);
sum+=a[i];}
max=a[0];
for(int i=0;i<n;i++)
if (max<a[i])
max=a[i];
for(int i=0;i<n;i++)
ct[a[i]]+=1;
for(int i=1;i<=max;i++)
ct[i]+=ct[i-1];
for(int i=n-1;i>=0;i--)
b[--ct[a[i]]]=a[i];
if (sum%3==0)
goto print;
else if (sum%3==1) {
for(int i=n-1;i>=0;i--)
if (b[i]%3==1) {
b[i]=-1; f=1;
goto print;
}
}
else {
for(int i=n-1;i>=0;i--)
if (b[i]%3==2) {
b[i]=-1; f=1;
goto print;
}
}
if (f==0&&sum%3==1) {
for(int i=n-1;i>=0&&c<2;i--)
if (b[i]%3==2) {
b[i]=-1;
c++;
}
}
if (f==0&&sum%3==2) {
for(int i=n-1;i>=0&&c<2;i--)
if (b[i]%3==1) {
b[i]=-1;
c++;
}
}
print:
for(int i=n-1;i>=0;i--)
if (b[i]!=-1)
printf("%d",b[i]);
return 0;
}
Не могли бы вы улучшить свой ответ, объяснив, что вы делаете? Один только код не является хорошим ответом.
Я надеюсь, что редактирования достаточно, чтобы объяснить код. @thebusybee
Пожалуйста, покажите, как ваше описание соответствует источнику. Например, я не могу найти очистку очередей и сортировку на шаге 9, если к этому перейти на шаге 6. -- Кроме того, ваш источник очень, очень плотный и за ним трудно следить. Пожалуйста, просмотрите несколько стилей кода, выберите один и придерживайтесь его. Имена ваших переменных должны быть более описательными. (Я написал такой код, когда начал работать с C много лет назад; тем временем я на горьком опыте убедился, что это ошибка.)
извините за эту мою ошибку, я сильно изменил исходный код. я просто помещаю все отсортированные элементы в массив b и проверяю остаток от суммы всех элементов, если он равен 1, я использую цикл for для обхода массива b и проверяю, является ли b[i]%3==1, и заменяю его на -1 если нет доступных элементов для замены, я заменяю 2 элемента b[i]%3==2, используя флаг f. То же самое касается суммы%3==2. если сумма% 3 == 0, я просто печатаю массив в обратном порядке. для других я печатаю все элементы, кроме -1, в обратном порядке, чтобы получить наибольшее кратное 3 из массива цифр. @thebusybee
Я новичок в кодировании. Прошел всего месяц с тех пор, как я поступил в колледж. Я никогда раньше не занимался программированием. Теперь я не только учусь кодировать на c, но и кодировать структуры данных на c.
Поскольку массив содержит только однозначные числа, вам не нужны три очереди. Что вам нужно, так это гистограмма цифр.