Алгоритм поворота массива за линейное время
Все здесь проделали большую работу, объяснив, как работает код, и продемонстрировали, как вы можете построить свои собственные примеры, но вот информационный теоретический ответ, показывающий, почему мы можем разумно ожидать, что существует решение, которое в конечном итоге найдет поиск методом перебора.
26 различных строчных букв образуют наш алфавит Σ. Чтобы позволить генерировать слова различной длины, мы дополнительно добавляем символ-терминатор ⊥, чтобы получить расширенный алфавит Σ' := Σ ∪ {⊥}.
Пусть α будет символом, а X - равномерно распределенной случайной величиной по Σ'. Вероятность получения этого символа P(X = α) и его информационное содержание I(α) определяются как:
P (X = α) = 1 / | Σ '| = 1/27
I (α) = -log₂ [P (X = α)] = -log₂ (1/27) = log₂ (27)
Для слова ω ∈ Σ* и его ⊥- прекращено аналог ω' := ω · ⊥ ∈ (Σ')*, мы имеем
I (ω): = I (ω ') = | ω' | * log₂ (27) = (| ω | + 1) * log₂ (27)
Поскольку генератор псевдослучайных чисел (PRNG) инициализируется с помощью 32-разрядного начального числа, мы можем ожидать, что большинство слов длина до
λ = пол [32 / log₂ (27)] - 1 = 5
для формирования по крайней мере одним начальным числом. Даже если бы мы искали слово из 6 символов, мы все равно добились бы успеха в 41,06% случаев. Не слишком потертый.
Для 7 букв мы смотрим ближе к 1,52%, но я не осознавал этого, прежде чем дать ему попробовать:
#include
#include
int main()
{
std::mt19937 rng(631647094);
std::uniform_int_distribution dist('a', 'z' + 1);
char alpha;
while ((alpha = dist(rng)) != 'z' + 1)
{
std::cout << alpha;
}
}
См. Вывод: http: // ideone .com / JRGb3l [+1126]
8 ответов
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package rotateinlineartime;
/**
*
* @author Sunshine
*/
public class Rotator {
void reverse(int a[], int n) {
for (int i = 0; i <= n - 1; i++) {
int temp;
temp = a[i];
a[i] = a[n - 1];
a[n - 1] = temp;
n--;
}
printArray(a);
}
void printArray(int a[]) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
Мое решение с Java
static int[] rotLeft(int[] a, int d) {
for (int i = 0; i < d; i++) {
oneRotation(a);
}
return a;
}
static void oneRotation(int[] a) {
int firstElement = a[0];
for (int i = 0; i < a.length - 1; i++) {
a[i] = a[i + 1];
}
a[a.length - 1] = firstElement;
}
O(1) метод достижения этого в python:
class OffsetList(list):
__slots__ = 'offset'
def __init__(self, init=[], offset=-1):
super(OffsetList, self).__init__(init)
self.offset = offset
def __getitem__(self, key):
return super(OffsetList, self).__getitem__(key + self.offset)
def __setitem__(self, key, value):
return super(OffsetList, self).__setitem__(key + self.offset, value)
def __delitem__(self, key):
return super(OffsetList, self).__delitem__(key + self.offset)
def index(self, *args):
return super(OffsetList, self).index(*args) - self.offset
Это основано на ответе об использовании списка на основе 1 в python .
Это имеет небольшой недостаток: если вы попытаетесь проиндексировать элемент за пределами списка, он вернет элементы с начала (нового), и отрицательные значения меньше размера, за вычетом смещения, работать не будет.
/* Q: How can we shift/rotate an array in place?
A: "in place" means O(1) space complexity, so we need to do some trick
*/
#include <iostream>
#include <algorithm>
using namespace std;
void ArrayRotate(int a[], int n, int k)
{
if (n < 1 || k % n == 0 ) return;
k %= n;
if (k < 0) k += n;
reverse(a, a+k);
reverse(a+k, a+n);
reverse(a, a+n);
}
void PrintArray(int a[], int n)
{
for ( int i = 0 ; i < n; ++i)
cout << a[i] << " ";
cout << endl;
}
int main()
{
int a[] = { 1, 2 , 3, 4, 5 };
int n = sizeof(a)/sizeof (a[0]);
PrintArray(a, n);
ArrayRotate(a, n, 2);
PrintArray(a, n);
return 0;
}
/* Output:
1 2 3 4 5
3 4 5 1 2
*/
Наивная реализация псевдокода:
for (n = 0; n < i; n++) {
for (j = array.length-1; j > n; j--)
swap(j, j-1)
}
Неоднократно перемещает последний элемент вперед, останавливаясь, прежде чем он перемещает что-либо ранее перемещенное вперед
Используя линейное время O (2N + m) и постоянное пространство O (4). m = GCD (n, p)
Это до 50% быстрее, чем подход подкачки, потому что подкачка требует записи O (N) раз во временную.
http://www.eis.mdx.ac.uk/staffpages/r_bornat/oldteaching/I2A/slides%209%20circshift.pdf
for (m=0, count=0; count!=n; m++) {
type t=A[m];
for (i=m, j=m+p; j!=m; i=j, j = j+p<n ? j+p : j+p-n, count++)
A[i]=A[j];
A[i]=t; count++;
}
Скажем, у нас есть функция под названием arr_reverse(arr,i,j), которая переворачивает элементы массива arr между индексами i и j, используя функцию swap.
Пример:
arr = {1,2,3,4,5}
i = 0
j = 2
, тогда функция вернется:
{3,2,1,4,5}
^^^^^
Реализация этой функции проста и равна O(N).
Теперь давайте использовать эту функцию для вращения массива.
arr = {1,2,3,4,5} // input array
k = 2 // amount of right rotation
result = {4,5,1,2,3} // expected result
l = 5 // length of array.
Step 1: Call arr_reverse(arr,l-k,l-1) which is arr_reverse(arr,3,4)
we get {1,2,3,5,4}
^^^
Step 2: Call arr_reverse(arr,0,l-k-1) which is arr_reverse(arr,0,2)
we get {3,2,1,5,4}
^^^^^
Step 3: Call arr_reverse(arr,0,l-1) which is arr_reverse(arr,0,4)
we get {4,5,1,2,3}
^^^^^^^^^
Весь процесс использует arr_reverse 3 раза, делая его O(N)
Короткий Ответ (код Python)
def reverse(arr, i, j):
for idx in xrange((j - i + 1) / 2):
arr[i+idx], arr[j-idx] = arr[j-idx], arr[i+idx]
def solution(A, K):
l = len(A)
if l == 0:
return []
K = K%l
reverse(A, l - K, l -1)
reverse(A, 0, l - K -1)
reverse(A, 0, l - 1)
return A
Длинный Ответ (объяснение кода)
Позволил мне говорить сначала основной случай с K < N, идея в этом случае состоит в том, чтобы разделить массив в двух частях A и B, A, первое N-K массив элементов и B последнее K элементы. реверс алгоритма A и B отдельно и наконец инвертирует полный массив (с двумя частями, инвертированными отдельно). Для управления случаем с [1 115] думайте, что каждый раз Вы инвертируете массив N времена, Вы получаете исходный массив снова, таким образом, мы можем просто использовать оператор модуля для нахождения, где разделить массив (инвертирующий только действительно полезные времена, избежав бесполезного смещения).
А графический пошаговый пример может помочь пониманию лучше понятие. Обратите внимание, что
- полужирная строка указывает на точку разделения массива (K = 3 в этом примере);
- два красных массива указывают, соответственно, на вход и ожидаемый вывод.
Запуск с:
взгляд, который, что мы хотим перед окончательным результатом, будет последними 3 инвертированными буквами, на данный момент реверс, которому позволяют, это на месте (первый реверс алгоритма):
теперь инвертируют первые элементы N-K (второй реверс алгоритма):
у нас уже есть решение, но в противоположном направлении, мы можем решить его инвертирующий целый массив (треть и продержаться реверс алгоритма):
Здесь окончательный результат, исходный массив, цикличный повернутый с [1 117].
Позволяют, дают также другой пошаговый пример с кодом Python, начинающим с:
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
K = 22
N = len(A)
мы находим индекс разделения:
K = K%N
#2
, потому что в этом случае первые 20 сдвигов будут бесполезны, теперь мы инвертируем последнее K (2) элементы исходного массива:
reverse(A, N-K, N-1)
# [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
, как Вы видите 9 и 10, был сдвиг, теперь мы инвертируем первые элементы N-K:
reverse(A, 0, N-K-1)
# [8, 7, 6, 5, 4, 3, 2, 1, 10, 9]
И, наконец, мы инвертируем полный массив:
reverse(A, 0, N-1)
# [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]
Примечание, что инвертирование массива имеет временную сложность O (N).