BG Development


Страници: (2) [1] 2   ( Първото ново мнение ) Reply to this topicStart new topicStart Poll

> Rotate array with space O(1)
cracker.
Публикувано на: 13-12-2023, 11:20
Quote Post



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

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



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

Имаме масив и число 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
PMEmail Poster
Top
ici
Публикувано на: 13-12-2023, 12:01
Quote Post


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

Мнения: 18494
Регистриран на: 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]
>>>


--------------------
Ние не сме в една лодка, ние сме в една буря. Лодките са различни.

Следващият път когато се почувстваш ненужен, грозен и недооценен, помни че освен това си и тъп.
PMEmail PosterUsers Website
Top
ici
Публикувано на: 13-12-2023, 12:12
Quote Post


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

Мнения: 18494
Регистриран на: 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]
>>>


--------------------
Ние не сме в една лодка, ние сме в една буря. Лодките са различни.

Следващият път когато се почувстваш ненужен, грозен и недооценен, помни че освен това си и тъп.
PMEmail PosterUsers Website
Top
cracker.
Публикувано на: 13-12-2023, 12:25
Quote Post



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

Мнения: 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]
>>>

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

Жив и здрав.
PMEmail Poster
Top
ici
Публикувано на: 13-12-2023, 13:08
Quote Post


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

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



Един ред:
CODE
a.append(a.pop(0))


--------------------
Ние не сме в една лодка, ние сме в една буря. Лодките са различни.

Следващият път когато се почувстваш ненужен, грозен и недооценен, помни че освен това си и тъп.
PMEmail PosterUsers Website
Top
cracker.
Публикувано на: 13-12-2023, 14:46
Quote Post



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

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



QUOTE (ici @ 13-12-2023, 13:08)
Един ред:
CODE
a.append(a.pop(0))

пробвах да трия елемента и да го инсертвам на позиция надолу с 2 от брояча в цикъла.Проблемът е, че като разместя елементите и цикъла си продължи напред явно изпуска някой елемент и дава грешен резултат.Мъча я, докато няма клиенти в заведението на служебния ПЦ, ако стигна до решение ще го пусна, ако евентуално някой друг начинаещ се пули на този проблем ;д.
PMEmail Poster
Top
ici
Публикувано на: 13-12-2023, 14:54
Quote Post


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

Мнения: 18494
Регистриран на: 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]
>>>


--------------------
Ние не сме в една лодка, ние сме в една буря. Лодките са различни.

Следващият път когато се почувстваш ненужен, грозен и недооценен, помни че освен това си и тъп.
PMEmail PosterUsers Website
Top
cracker.
Публикувано на: 15-12-2023, 00:41
Quote Post



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

Мнения: 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те дадени теста в условието, тествайте и с ваши входове, ако е нужно, че да не се изложим ;д ! icon_smile.gif

Всичко добро, благодаря на Ици още веднъж.
PMEmail Poster
Top
Bender++
Публикувано на: 15-12-2023, 11:49
Quote Post



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

Мнения: 499
Регистриран на: 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


--------------------
Слава на Цар Путин! Долу украинските фашисти!
PMEmail Poster
Top
cracker.
Публикувано на: 15-12-2023, 13:20
Quote Post



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

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



Благодаря, Бендер.
Аз бях сигурен, че решението ми е бозаво, щото ми дойде набързо, наплясках го видях че минава тестовете дето бяха дадени и реших аз съм чоека ;д. Даже не съм направил и проверка за празен масив при входа.
Мерси за платформата, светнах яко хаха. Твоето решение е нещо друго вече.

Живи и здрави! icon_smile.gif
PMEmail Poster
Top
1 потребители преглеждат тази тема в момента (1 гости, 0 анонимни потребители)
Потребители, преглеждащи темата в момента:

Topic Options Страници: (2) [1] 2  Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2019 | BG Development | All Rights Reserved
RSS 2.0