BG Development Форуми -> Rotate array with space O(1)

BG Development · За реклама · За контакти

Помощ

Търсене

Потребители

Календар

Правила

Здравей! ( Включване | Регистриране )

BG Development Форуми -> Програмиране -> PHP/Perl/Python/ASP

Страници: (2) [1] 2 ( Първото ново мнение )

Rotate array with space O(1)

Абонирай се за темата | Изпрати адреса на темата на приятел | Принтирай темата

cracker.

Публикувано на: 13-12-2023, 11:20

Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 26
Регистриран на: 13.11.23

Здравейте, някой занимава ли му се да ми даде лек хинт как да стане номера, че ако потърся инфо в нета излиза и кода на задачата, а видя ли го леко се обезсмисля филмът

.

Имаме масив и число d.Трябва да завъртим всеки елемент наляво d пъти.С нов лист е лесно.Искам да го реша най-оптимално от към space, една-две променливи за временни холдъри на елементите в ротация мисля че ще стигнат.

Проблемът ми е, че когато завъртя така, един вид ротейт-вам елемента с индекс i, ма тоя, на чието место отива елемента i трябва да се върне и той две места назад, а върна ли него губя този, на чието място ще отиде той и т.н.

CODE

temp = arr[i];
arr[i] = arr[i-d];
arr[i-d] = arr[i];

Не знам дали описах всичко, което си мисля, правилно - дано сте ме разбрали.
Всеки съвет и насока е добре дошла.
Благодаря предварително!
Лек ден!

п.с О(1)* в заглавието

Това мнение е било редактирано от cracker. на 13-12-2023, 11:25

ici

Публикувано на: 13-12-2023, 12:01

Име: Ивайло Илчев
Група: VIP
Ранг: Почетен член

Мнения: 19077
Регистриран на: 06.06.04

CODE

import numpy as np

x = np.arange(10)

print(x)

print(np.roll(x, 2))

print(np.roll(x, -2))

QUOTE

*** Remote Interpreter Reinitialized ***
[0 1 2 3 4 5 6 7 8 9]
[8 9 0 1 2 3 4 5 6 7]
[2 3 4 5 6 7 8 9 0 1]
>>>

--------------------

Facebook is a bit like checking your underwear after a fart.
Most likely there's nothing new and if there is it's probably shit.

ici

Публикувано на: 13-12-2023, 12:12

Име: Ивайло Илчев
Група: VIP
Ранг: Почетен член

Мнения: 19077
Регистриран на: 06.06.04

CODE

>>> a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> b = a[0]
>>> del a[0]
>>> a.append(b)
>>> a
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
>>>

--------------------

Facebook is a bit like checking your underwear after a fart.
Most likely there's nothing new and if there is it's probably shit.

cracker.

Публикувано на: 13-12-2023, 12:25

Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 26
Регистриран на: 13.11.23

QUOTE (ici @ 13-12-2023, 12:12)

CODE

>>> a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> b = a[0]
>>> del a[0]
>>> a.append(b)
>>> a
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
>>>

страшен си, Ици.

Жив и здрав.

ici

Публикувано на: 13-12-2023, 13:08

Име: Ивайло Илчев
Група: VIP
Ранг: Почетен член

Мнения: 19077
Регистриран на: 06.06.04

Един ред:

CODE

a.append(a.pop(0))

--------------------

Facebook is a bit like checking your underwear after a fart.
Most likely there's nothing new and if there is it's probably shit.

cracker.

Публикувано на: 13-12-2023, 14:46

Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 26
Регистриран на: 13.11.23

QUOTE (ici @ 13-12-2023, 13:08)

Един ред:

CODE

a.append(a.pop(0))

пробвах да трия елемента и да го инсертвам на позиция надолу с 2 от брояча в цикъла.Проблемът е, че като разместя елементите и цикъла си продължи напред явно изпуска някой елемент и дава грешен резултат.Мъча я, докато няма клиенти в заведението на служебния ПЦ, ако стигна до решение ще го пусна, ако евентуално някой друг начинаещ се пули на този проблем ;д.

ici

Публикувано на: 13-12-2023, 14:54

Име: Ивайло Илчев
Група: VIP
Ранг: Почетен член

Мнения: 19077
Регистриран на: 06.06.04

Виж какво става тук:

CODE

a = [x for x in range(10)]

for i, x in enumerate(a):
print(i, x)
del a[i]
print(a)

QUOTE

*** Remote Interpreter Reinitialized ***
0 0
1 2
2 4
3 6
4 8
[1, 3, 5, 7, 9]
>>>

--------------------

Facebook is a bit like checking your underwear after a fart.
Most likely there's nothing new and if there is it's probably shit.

cracker.

Публикувано на: 15-12-2023, 00:41

Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 26
Регистриран на: 13.11.23

Едва ли някой от опитните тигри тук му трябва решението, но ако някой случаен начинаещ му е нужно, ето:

CODE

def rotate(arr,rotation_amount):
lenght_of_array = len(arr);
for currentIndex in range(0,rotation_amount):
arr[currentIndex],arr[currentIndex-2] = arr[currentIndex-2],arr[currentIndex];

for currentIndex in range(rotation_amount,(lenght_of_array-rotation_amount)):
arr[currentIndex],arr[currentIndex-2] = arr[currentIndex-2],arr[currentIndex]
if currentIndex == (lenght_of_array-rotation_amount) - 1:
arr[currentIndex],arr[currentIndex-1] = arr[currentIndex-1],arr[currentIndex]
return arr

test_array = [1,3,5,7,9];
rotate(test_array,2)

Върти на ляво, направих само 3те дадени теста в условието, тествайте и с ваши входове, ако е нужно, че да не се изложим ;д !

Всичко добро, благодаря на Ици още веднъж.

Bender++

Публикувано на: 15-12-2023, 11:49

Име:
Група: Потребител
Ранг: Старо куче

Мнения: 608
Регистриран на: 18.04.21

Този проблем има доста по-добро решение:

CODE

pub fn rotate_right(nums: &mut Vec<i32>, k: i32) {
let n = nums.len() as i32;
let k = (k % n) as usize;
nums.reverse();
nums[..k].reverse();
nums[k..].reverse();
}

Ротацията на ляво е еквивалентна на ротация на дясно със стъпка "array_length - k"

Иначе съм сигурен, че твоето решение не работи, защото при "наивна" ротация се получават "цикли", и твоето решение дори не ги споменава

CODE

pub fn rotate(nums: &mut Vec<i32>, k: i32) {
let k = k as usize % nums.len();
if nums.len() <= 1 || k == 0 {
return;
}

// It's more efficient :)
if nums.len() == k * 2 {
rotate_half(nums);
return;
}

let cycle = gcd(nums.len(), k);
rotate_cycle(nums, k, cycle);
}

fn rotate_half(nums: &mut Vec<i32>) {
let h_len = nums.len() / 2;
for i in 0..h_len {
nums.swap(i, i + h_len);
}
}

fn rotate_cycle(nums: &mut Vec<i32>, k: usize, cycle: usize) {
let m = nums.len() / cycle;

for i in 0..cycle {
let mut tmp = nums[i];
let mut idx = i;

for _ in 0..m {
idx = (idx + k) % nums.len() as usize;
std::mem::swap(&mut tmp, &mut nums[idx]);
}
}
}

fn gcd(mut a: usize, mut b: usize) -> usize {
while b != 0 {
let t = b;
b = a % b;
a = t;
}

a
}

Може да си тестваш решението ето тук: https://leetcode.com/problems/rotate-array/
Ще ти хване corner-case-овете

Това мнение е било редактирано от Bender++ на 15-12-2023, 11:55

--------------------

Слава на Цар Путин! Долу украинските фашисти!

cracker.	Публикувано на: 15-12-2023, 13:20
Име: Група: Потребител Ранг: Новопостъпил Мнения: 26 Регистриран на: 13.11.23	Благодаря, Бендер. Аз бях сигурен, че решението ми е бозаво, щото ми дойде набързо, наплясках го видях че минава тестовете дето бяха дадени и реших аз съм чоека ;д. Даже не съм направил и проверка за празен масив при входа. Мерси за платформата, светнах яко хаха. Твоето решение е нещо друго вече. Живи и здрави!

0 потребители преглеждат тази тема в момента (0 гости, 0 анонимни потребители)

Потребители, преглеждащи темата в момента:

« Предишна тема | PHP/Perl/Python/ASP | Следваща тема »

Страници: (2) [1] 2

BG Development Форуми -> Програмиране -> PHP/Perl/Python/ASP