Рубрики

Следующее большее число на основе старшинства цифр

Дано число num, содержащее n цифр. Проблема состоит в том, чтобы найти следующее большее число, используя тот же набор цифр в num на основе заданного приоритета цифр. Например, приоритет цифр задается как 1, 6, 4, 5, 2, 9, 8, 0, 7, 3, что просто означает 1 <6 <4 <5 <2 <9 <8 <0 <7 <3 , Если следующий больший номер не может быть сформирован, напечатайте оригинальный номер.

Примеры:

Input : num = "231447"
        pre[] = {1, 6, 7, 5, 2, 9, 8, 0, 4, 3}
Output : 237144
According to the precedence of digits 1 is 
being considered as the smallest digit and 3
is being considered as the largest digit.

Input : num = "471"
        pre[] = {1, 6, 7, 5, 2, 9, 8, 0, 4, 3}
Output : 471

Подход: следующие шаги:

  1. Создайте массив с приоритетом [] размером '10'. С помощью массива приоритетов pre [] назначьте номер приоритета каждой цифре в приоритете [], где «1» рассматривается как наименьший приоритет, а «10» — как наивысший приоритет.
  2. Используя STL C ++ next_permutation с определенной вручную функцией сравнения, найдите следующую большую перестановку.
  3. ,

// реализация C ++ для поиска следующего большего числа
// на основе старшинства цифр
#include <bits/stdc++.h>

  

using namespace std;

  
#define DIGITS 10

  
// priority [] для сохранения приоритета цифр
// на основе массива pre []. Здесь «1»
// рассматривается как наименьший приоритет как '10' как
// самый высокий приоритет

int priority[DIGITS];

  
// функция компаратора, используемая для нахождения
// следующая большая перестановка

struct compare {

  bool operator()(char x, char y) {

    return priority[x - '0'] < priority[y - '0'];

  }

};

  
// функция для поиска следующего большего числа
// на основе старшинства цифр

void nextGreater(char num[], int n, int pre[]) {

  memset(priority, 0, sizeof(priority));

  

  // переменная для присвоения приоритетов цифрам

  int assign = 1;

  

  // назначаем приоритеты цифрам на

  // основа пред []

  for (int i = 0; i < DIGITS; i++) {

    priority[pre[i]] = assign;

    assign++;

  }

  

  // найти следующую большую перестановку 'num'

  // используя функцию сравнения ()

  bool a = next_permutation(num, num + n, compare());

  

  // если следующая большая перестановка не существует

  // затем сохраняем исходный номер обратно в 'num'

  // используя 'pre_permutation'.

  if (a == false)

    prev_permutation(num, num + n, compare());

}

  
// Программа драйвера для тестирования выше

int main() {

  char num[] = "231447";

  int n = strlen(num);

  int pre[] = {1, 6, 7, 5, 2, 9, 8, 0, 4, 3};

  nextGreater(num, n, pre);

  cout << "Next Greater: " << num;

  return 0;

}

Выход:

Next Greater: 237144

Сложность времени: O (n).
Вспомогательное пространство: O (1).

Рекомендуемые посты:

Следующее большее число на основе старшинства цифр

0.00 (0%) 0 votes