Вывод перестановки при вводе вектора инверсии

Question

Мне нужно знать, как печатать перестановку при вводе чего-то типа X = [5 0 1 1 1 2], где 5 = n aka количество целых чисел, следующих в массиве. Результат прост, это будет J = [5 1 2 4 3]. Это получается путем считывания X с конца, начинающегося с 2. В N (1-5) больше, чем 2. Таким образом, J[5] теперь равно 3. Затем переместите X в 1 до 2, там будет 1 номер в (1-5) - (3 (получено ранее)) спереди больше, чем J[4], поэтому J[4] = 4. Если это не имеет смысла из-за моего объяснения, это может помочь, когда 3 было удалено, теперь это 1 2 4 5. Итак, если только один элемент больше самого себя, он должен быть элементом 4, потому что только 5 больше. У меня есть это до сих пор, и я запутываю себя над кодированием чего-то, что кажется таким простым.

public static void main(String[] args) { 

    int i; 
    int j; 

    Scanner input = new Scanner(System.in); 
    int nums = input.nextInt(); 

    if (nums < 1 || nums > 1000) { 
     input.close(); 
    } else { 
     for (int counter = 0; counter < nums; counter++) { 
      int[] a = new int[nums]; 
      int[] w = new int[nums]; 
     } 
    } 
} 

Answer 1

Я дам вам подход к тому, как я буду заниматься этой проблемой.

Таким образом, ввод вы получите от этой формы:

X = [5 0 1 1 1 2]; 
//5 signifies list of numbers [1,2,3,4,5] 
//And the rest of the array i.e. X[1] to X[4] gives us a permutation 

Предположим, у вас есть ArrayList из n чисел. Я предложил использовать arraylist, потому что мне легче работать с ними, так как нам придется удалять элементы здесь.

Так первоначально ArrayList имеет следующее содержание (гарантировать, что элементы вводятся в порядке возрастания):

foo = {1,2,3,4,5}; //Assuming the array list is called foo 

//The permutation array is [0,1,1,1,2] in your case 
//Start traversing it backwards, you can do that with a simple loop 
//So given the array a = [0,1,1,1,2], you start with a[4] 

a[4] = 2; 
//This implies the number you are looking for is at the 3rd last position of the array list 

Выше суть решения. Поскольку список массивов отсортирован, и мы хотим найти номер, который имеет только 2 или a[4] цифры, превышающие его. Это просто отсчет с 5,4 до 3-го элемента, который равен 3. Затем вы удаляете этот элемент и продолжаете следующую итерацию.

Проще говоря:

l = foo.size(); //Length of array list initialized before the loop 
//If you have a loop starting from i=4 to 0 for the array [0,1,1,1,2] 
//At any i, you do: 
index = l - a[i]; 
System.out.print(foo.get(index)); 
//This would ultimately output 3 4 2 1 5 in your case 

foo.remove(index); //Remove the element at this index from arraylist 
l = l-1; //Since at every iteration we will remove one element 

В сущности, это просто с помощью перестановки, чтобы найти правильный индекс элемента в отсортированном ArrayList и удалить его и идти вперед с итерациями. Надеюсь, я смог четко объяснить себя, и это заставляет вас начать в правильном направлении.

PS: Я уже предоставил отправную точку для вашего кода, должен быть хорошим упражнением для вас, чтобы попробовать.