CodingQuestion, найти все пропущенные номера

Question

1) nums[i] != nums[nums[i]-1]
2) i != nums[i]-1

Есть ли разница между 1) и 2)?Я не могу понять разницу между ними, но вместо 1), если у меня есть код 2), программа имеет ошибку.

Вот краткое объяснение моей проблемы.Это проблема кодирования, которая находит все пропущенные числа в несортированном массиве, который содержит числа, взятые из диапазона от 1 до n.Массив может иметь дубликаты, так что это означает, что номера соума будут отсутствовать.(- который я хочу получить.)

Input: [2, 3, 1, 8, 2, 3, 5, 1] Output: 4, 6, 7 
The array should have all numbers from 1 to 8, due to duplicates 4, 6, and 7 are missing.

Я знаю, что есть определенно более эффективные решения для этой проблемы, но здесь я хочу решить это, используя шаблон циклической сортировки, который использует тот факт, что

В этой задаче числа находятся в диапазоне от «1» до «n», поэтому мы можем разместить каждое число в правильном месте.например, индекс 0: 1 / индекс 1: 2 / индекс 2: 3 .... и т. д.

public static List<Integer> findNumbers(int[] nums) {
int i = 0;
while (i < nums.length) {
  if (nums[i] != nums[nums[i] - 1])
    swap(nums, i, nums[i] - 1);
  else
    i++;
}

List<Integer> missingNumbers = new ArrayList<>();
for (i = 0; i < nums.length; i++)
  if (nums[i] != i + 1)
    missingNumbers.add(i + 1);

return missingNumbers;   }

Итак, возвращаясь к моему вопросу, я не могу найти никакой разницы между 1) и2).Потому что всегда индекс 0 должен иметь 1, индекс 1 должен иметь 2, индекс 2 должен иметь 3. так что я думаю, что я могу просто использовать шаблон: 2) i! = Nums [i] -1 вместо 1).

Я что-то пропустил?

Answer 1

while (i < nums.length) {
  if (nums[i] != nums[nums[i] - 1])
    swap(nums, i, nums[i] - 1);
  else
    i++;
}

Давайте разберемся, что может пойти не так в этом решении.Алгоритм получил значение 10 элемента 0 и значение элемента 9 (потому что nums[i] - 1 равно 9).пусть это будет 10 например.И алгоритм идет вперед, потому что значения равны.Как видите, это ответ на ваш вопрос:

nums[i] != nums[nums[i]-1] - сравнивает со случайным числом из исходного массива.Это вызывает очень забавный бесконечный цикл для вашего примера и цифры 2 и 3 на первых двух позициях.

i != nums[i] - 1 - сравнивает текущее значение с индексом, который действительно должен быть помещен в эту позицию.

Также вы можете легко получить IndexOutOfBoundsException, если массив будет иметь длину меньше максимального числа.Но, насколько я понимаю, это не является частью упражнения.

Как я вижу, вы пытаетесь решить проблему без дополнительного массива.Но вы можете найти более простое решение здесь https://javarevisited.blogspot.com/2018/04/how-to-find-k-missing-numbers-in-array-java.html

Answer 2

Условия ниже не совпадают -

1) nums[i] != nums[nums[i]-1] 2) i != nums[i]-1

Пример:

let i = 0
const nums = [2, 3, 1, 8, 2, 3, 5, 1];

nums[i] != nums[nums[i]-1];
nums[0] != nums[nums[0]-1];
2 != nums[2-1];
2 != 3; 

Здесь вы проверяете элемент по текущему индексу с элементом по следующему индексу.

i != nums[i]-1
0 != nums[0]-1;
0 != 2-1
0 != 1;

В этом случае вы проверяете, не равен ли current index элементу текущего индекса в массиве минус один.

Ваша логика not equal to не будет работать. Для правильной сортировки необходимо использовать greater than(>) or less than(<). Для возрастания порядок замены должен выполняться только в том случае, если текущий элемент индекса больше следующего.