Проверьте, является ли вхождение индивидуальной цифры в число одинаковым или нет
Нам необходимо проверить, является ли вхождение отдельной цифры в число одинаковым или нет. Например, для 2244 (2 встречаются 2 раза и 4 встречаются 2 раза). Следовательно, встречаемость обеих цифр одинакова.
//This will return true if occurrence of individual digit in
//a number is same else false
bool stable(int no)
{
vector<int> v1;
int k , count = 1;
int arr[10];
//Initializing all arr[] -> 0
for(int k = 0 ; k < 10 ;k++)
{
arr[k] = 0;
}
while(no != 0)
{
k=no%10;
arr[k]++;
no=no/10;
}
for(int i = 0 ; i < 10 ; i++)
{
if(arr[i] != 0)
{
v1.push_back(arr[i]); //storing count of individual digits
}
}
vector<int>::iterator it , it2;
for(it = v1.begin()+1 ,it2 = v1.begin(); it != v1.end() ; it++,it2++)
{
if(*it == *it2) //if all the values are same return true else false
{
count++;
}
}
if(count == v1.size()) return true;
return false;
}
Но этот код не работает, как 2222,1111,444. Кроме того, не могли бы вы предложить какой-нибудь хороший способ оптимизации кода?
Решение
Я думаю, что вы делаете это сложнее, чем нужно (или я серьезно неправильно понимаю вопрос, который часто случается).
Предполагается, что требования являются такими, как указано: Если задано ненулевое положительное значение, число квалифицируется, если все цифры появляются с одинаковой частотой, включая 1 (например, 1122, 2222, 1234 все соответствуют, поскольку ни одна цифра не имеет более высокую частоту, чем любая Другой).
Алгоритм прост:
- Быстрый возврат на любое значение менее 10; однозначный номер сразу уточняется.
- Построить счетчик массив остатков модуля.
- Найти первое ненулевое значение в массиве
- С этого момента найдите первое ненулевое значение, которое НЕ соответствует значению из (4). Если вы достигли конца последовательности, не обнаружив такой разницы, все цифры в исходном номере должны иметь одинаковое количество.
Во всей сложности логарифмическое основание-10 для входного числа плюс однопроходное сканирование массива постоянного размера (10 элементов).
Пример кода
#include <algorithm>
#include <iterator>
bool stable(unsigned value)
{
if (value < 10) // single digit only, including zero
return true;
unsigned ar[10]={0};
do { ++ar[value%10]; }
while (value /= 10);
auto it = std::find_if(std::begin(ar), std::end(ar),
[](auto n) { return n != 0; });
return std::find_if(std::next(it), std::end(ar),
[it](auto n){ return n && (n != *it);}) == std::end(ar);
}
Вы всегда можете продвинуть это, сохранив максимальное количество цифр и оставив без операций поиска, если в конечном итоге оно будет равно 1 (например, 1234, 102938 являются такими примерами). Я оставлю это в качестве упражнения для сравнения с вами, чтобы определить, есть ли какой-либо выигрыш в производительности. Я честно сомневаюсь, что будет.
Другие решения
Попробуй это:
bool stable(int no)
{
std::vector<int> v1;
while (no != 0){
v1.push_back(no%10);
no /= 10;
}
std::sort(v1.begin(), v1.end()); //SORTING DIGITS IN ASCENDING ORDER
std::vector<int> index = {0}; //BUILDING VEC WITH INDEXES WHERE CHANGES HAPPEN
for (unsigned int i = 0; i < v1.size()-1; ++i){
if (v1[i] != v1[i+1])
index.push_back(i+1);
}
//EDGE CASE WHEN ONLY 1 DIGIT APPEARS (e.g. 555)
if (index.size() == 1)
return true;
//CHECKING THAT ALL INDEXES ARE EQUALLY SEPARATED
int diff = index[1] - index[0];
for (unsigned int i = 1; i < index.size()-1; ++i){
if (index[i+1] - index[i] != diff)
return false;
}
return true;
}
Проверяя, все ли повторяющиеся значения одинаковы, вы можете напрямую вернуться false если счет не совпадает, нет необходимости проверять дальше. Если вектор содержит только один отсчет для чисел, таких как 2222, 1111 это вернется true,
vector<int>::iterator it , it2;
for(it = v1.begin()+1 ,it2 = v1.begin(); it != v1.end() ; it++,it2++)
{
if(*it != *it2) //if two values are not same return false
{
return false;
}
}
return true;