Python program to put positive numbers at even indexes (0, // 2,.) and

Python program to put positive numbers at even indexes (0, // 2, 4,..) and
# negative numbers at odd indexes (1, 3, 5, ..)
 
# The main function that rearranges elements of given array.
# It puts positive elements at even indexes (0, 2, ..) and
# negative numbers at odd indexes (1, 3, ..).
def rearrange(arr, n):
# The following few lines are similar to partition process
# of QuickSort. The idea is to consider 0 as pivot and
# divide the array around it.
i = -1
for j in range(n):
if (arr[j] < 0):
i += 1
# swapping of arr
arr[i], arr[j] = arr[j], arr[i]

# Now all positive numbers are at end and negative numbers
# at the beginning of array. Initialize indexes for starting
# point of positive and negative numbers to be swapped
pos, neg = i+1, 0

# Increment the negative index by 2 and positive index by 1,
# i.e., swap every alternate negative number with next
# positive number
while (pos < n and neg < pos and arr[neg] < 0):
 
# swapping of arr
arr[neg], arr[pos] = arr[pos], arr[neg]
pos += 1
neg += 2
 
# A utility function to print an array
def printArray(arr, n):

for i in range(n):
print arr[i],

# Driver program to test above functions
arr = [-1, 2, -3, 4, 5, 6, -7, 8, 9]
n = len(arr)
rearrange(arr, n)
printArray(arr, n)
 
# Contributed by Afzal


3
Oddiy usul - barcha elementlarni birma-bir yig'ish. Har bir tanlangan element uchun uning paydo bo'lishini qatorni bosib o'ting, agar hisoblash n / k dan oshsa, elementni chop eting. Ushbu usulning vaqt murakkabligi O (n2) bo'ladi.
Yaxshi echim - saralashdan foydalanish. Birinchidan, O (nLogn) algoritmi yordamida barcha elementlarni saralash. Massiv saralanganidan so'ng, biz barcha kerakli elementlarni qatorni chiziqli skanerlashda topishimiz mumkin. Shunday qilib, ushbu usulning vaqt murakkabligi O (nLogn) + O (n), ya'ni O (nLogn).
Quyidagi qiziqarli O (nk) echim:


Yuqoridagi muammoni O (k-1) qo'shimcha bo'shliq yordamida O (nk) vaqtida hal qilishimiz mumkin. E'tibor bering, chiqishda hech qachon k-1 elementlardan ko'proq bo'lishi mumkin emas (Nega?). Ushbu algoritmda asosan uchta bosqich mavjud.


1) Elementlarni va ularning sonlarini saqlash uchun vaqtincha (k-1) massiv yarating (Chiqish elementlari ushbu k-1 elementlari qatoriga kiradi). Quyida vaqtinchalik massiv elementlarining tuzilishi keltirilgan.
struct eleCount {
int element;
int count;
};
struct eleCount temp[];
) so'nggi (k-1) potentsial nomzodlar orqali takrorlang (temp [] da saqlanadi). yoki har bir element, aslida n / k dan oshganligini tekshiring. Ushbu qadam O (nk) vaqtni oladi.


Asosiy qadam - bu 2-qadam, potentsial nomzodlarni har bir nuqtada qanday saqlash kerak? 2-bosqichda ishlatiladigan qadamlar mashhur o'yinlarga o'xshaydi: Tetris. Biz har bir raqamni vaqtinchalik massiv tempida tushadigan Tetrisdagi parcha sifatida ko'rib chiqamiz []. Bizning vazifamiz bir xil ustunni bir xil ustunda saqlashga harakat qilishdir (vaqtinchalik qatorda hisoblash ko'paytiriladi).

Consider k = 4, n = 9
Given array: 3 1 2 2 2 1 4 3 3

i = 0
3 _ _
temp[] has one element, 3 with count 1

i = 1
3 1 _