Поменять местами два элемента массива без временной переменной
Реализуйте Swap(a, i, j), меняющую местами a[i] и a[j] НА МЕСТЕ БЕЗ временной переменной. Требования: предпочтите кортежный обмен (a[i], a[j]) = (a[j], a[i]). Если спросят про арифметический или XOR-трюк, отметьте, что они ломаются при i == j (обнуляют элемент). Обмен индекса с самим собой должен оставить массив без изменений.
public static void Swap(int[] a, int i, int j)
{
// ваш код здесь
}Допишите реализацию.
Кортежный обмен: (a[i], a[j]) = (a[j], a[i]). Правая часть вычисляется полностью до присваиваний, поэтому оба элемента меняются безопасно — даже при i == j, где просто перезаписывается то же значение. Не нужна временная переменная, и нет арифметического/XOR-трюка, обнуляющего элемент при самообмене.
- ✗Использовать XOR или сложение/вычитание, обнуляющие элемент при
i == j - ✗Считать арифметический обмен безопасным — он может переполнить
intна больших значениях - ✗Протаскивать две локальные копии — это просто переименованная временная переменная
- →Почему именно XOR-обмен обнуляет элемент при
i == j? - →Как кортежный обмен вычисляет правую часть до присваивания?
Задача
Поменять местами a[i] и a[j] без временной переменной.
public static void Swap(int[] a, int i, int j)
{
(a[i], a[j]) = (a[j], a[i]); // правая часть вычисляется первой
}Как это работает
Кортежное присваивание в C# сначала полностью вычисляет правую часть (a[j], a[i]) во временный кортеж, а затем распаковывает его обратно в a[i] и a[j]. Поэтому оба значения меняются местами одновременно и ни одно не теряется — отдельная временная переменная не нужна.
Важное преимущество — безопасность при i == j. Тогда обе стороны ссылаются на один элемент, и обмен просто перезаписывает его тем же значением: массив не меняется. «Хитрые» трюки без temp здесь ломаются:
- XOR (
a[i] ^= a[j]; a[j] ^= a[i]; a[i] ^= a[j];) приi == jделаетx ^ x = 0— элемент обнуляется. - Арифметика (
+/-) тоже обнуляет элемент приi == jи вдобавок может переполнитьintна больших значениях.
Кортежный обмен свободен от обеих ловушек, читается ясно и работает за O(1).
