наименее частое общее число из массива int

Я должен найти наименьшее общее число из массива int, я написал код, но он не работает должным образом,

Вот моя логика,
1. отсортировать массив
2. обновите общий счетчик минут
3. получить, если все уникальны

и код ниже,

static int min_loc ; //minimum value location
static int min_cnt ;
int all_uniqFlag = true;

void leastCommon(int data[],int n)
{
int rcount = 0; //Repeated number counter
int mcount = n; // minimum repetetion counter;

// The array is already sorted we need to only find the least common value.
for(int i = 0 ; i < n-1 ; i++)
{
//Case A : 1 1 2 2 2 3 3 3 3 4 5 5 5 5 : result should be 4
//Case B : 1 2 3 4 5 6 7 (All unique number and common values so all values should be printed
//                        and )
//Case C : 1 1 2 2 3 3 4 4 (all numbers have same frequency so need to display all )
cout << "data[i] : " << data[i] << " data[i+1] : " << data[i+1] <<  "i = " << i << endl;
if(data[i] != data[i+1])
{
//mcount = 0;
//min_loc = i;
//return;
}
if(data[i] == data[i+1])
{
all_uniqFlag = false;
rcount++;
}
else if(rcount < mcount)
{
mcount = rcount;
min_loc = i ;//data[i];
}
}
min_cnt = mcount;
}

Как упомянуто в комментарии, только Дело B работает, а Дело A и C не работает. Не могли бы вы помочь мне решить проблему?

1

Решение

  • просмотреть список
  • сравнить каждый элемент в списке с последним элементом в out массив
  • Если элемент соответствует, то увеличить его счетчик на 1
  • Если элемент не совпадает, добавьте новый элемент в out
    массив и приращение index на 1

После завершения сканирования out массив будет иметь все отдельные элементыout[][0] и их частоты out[][1]

  • Просканируйте список частот (out[][1]) найти самую низкую частоту
  • Наконец, сделайте еще одно сканирование списка элементов. out[][0] и печатать элементы, частота которых совпадает с самой низкой частотой

.

#include<stdio.h>
#include<stdlib.h>
#define N 8
int main()
{
//int data[N]={1,2,3,4,5,6,7};
int data[N]={1,1,2,2,3,3,4,4};
//int data[N]={1,1,2,2,2,3,3,3,3,4,5,5,5,5};
int out[N][2];
int i=0,index=0;
for(i=0;i<N;i++)
{
out[i][0]=0;
out[i][1]=0;
}
out[0][0] = data[0];
out[0][1]=1;
for(i=1;i<N;i++)
{
if(data[i] != out[index][0])
{
index++;
out[index][0] = data[i];
out[index][1] = 1;
}
else
{
out[index][1]++;
}
}

int min=65536;
for(i=0;i<N;i++)
{
if(out[i][1] == 0)
{
break;
}
if(out[i][1] < min)
{
min = out[i][1];
}
}
for(i=0;i<N;i++)
{
if(out[i][1] == min)
{
printf("%d\t",out[i][0]);
}
}
printf("\n");
}
1

Другие решения

Вы можете использовать map за это:

#include <string>
#include <map>
#include <iostream>

typedef std::map<int, int> Counter;

void leastCommon(int data[],int n) {
Counter counter;
int min = n;
for (int i = 0; i < n; i++)
counter[data[i]]++;
for (Counter::iterator it = counter.begin(); it != counter.end(); it++) {
if (min > it->second) min = it->second;
}
for (int i = 0; i < n; i++) {
if (counter[data[i]] == min) {
std::cout << data[i] << std::endl;
counter[data[i]]++;
}
}
}

int main() {
int data[] = {1, 1,3,4,4,2,4,3,2};
leastCommon(data, 9);
return 0;
}
1

Подход

  • выберите 1-й элемент из отсортированного массива, и пока последовательные элементы к нему одинаковы, сохраните их в output [] до тех пор, пока цикл не прервется
  • хранить частоту элемента в наименьшей частоте
  • выберите следующий элемент, проверьте его последовательные элементы и сохраните их в том же выводе [], пока цикл не прервется
  • проверьте частоту этого с наименьшей частотой
    • если то же самое, ничего не делайте (пусть они будут добавлены в вывод [])
    • если меньше, очистите output [] и сохраните тот же элемент no. времен
    • если больше, измените эффективную длину output [] на предыдущую длину перед итерацией для этого элемента
  • аналогичным образом выполните итерацию для всех различных элементов и, наконец, получите результат из output [] от 0 до эффективной длины

    void leastCommon(int data[], int len) {
    
    if ( len > 0) {
    int output[] = new int[len];
    int outlen = 0; // stores the size of useful-output array
    int leastFrequency = len; // stores the lowest frequency of elements
    
    int i=0;
    int now = data[i];
    while (i < len) {
    int num = now;
    int count = 0;
    do {
    output[outlen] = now;
    outlen++;
    count++;
    
    if((++i == len)){
    break;
    }
    now = data[i];
    } while (num == now);   // while now and next are same it adds them to output[]
    
    if (i - count == 0) { // avoids copy of same values to output[] for 1st iteration
    leastFrequency = count;
    } else if (count < leastFrequency) {  // if count for the element is less than the current minimum then re-creates the output[]
    leastFrequency = count;
    output = new int[len];
    outlen = 0;
    for (; outlen < leastFrequency; outlen++) {
    output[outlen] = num;   // populates the output[] with lower frequent element, to its count
    }
    } else if (count > leastFrequency) {
    outlen -= count;    // marks outlen to its same frequent numbers, i.e., discarding higher frequency values from output[]
    }
    }
    //for(int j = 0; j < outlen; j++) {
    // print output[] to console
    //}
    }
    }
    

Пожалуйста, предложите для улучшений.

1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector