We can determine how "out of order" an array A is by counting the number of inversions it has. Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element.
Given an array, count the number of inversions it has. Do this faster than O(N^2) time.
You may assume each element in the array is distinct.
For example, a sorted list has zero inversions. The array [2, 4, 1, 3, 5] has three inversions: (2, 1), (4, 1), and (4, 3). The array [5, 4, 3, 2, 1] has ten inversions: every distinct pair forms an inversion.
תשובות
הוסף תשובה
|
לצפיה בתשובות
ספטמבר 2021
I have an O(NlogN) solution:
For each element, calculate the difference in position between the sorted (asc) and unsorted array. If an element "moved left" by x, add x to the counter.
1. חיבור שני מספרים המיוצגים כמערך של ספרות
2. כתוב פונקציה המזהה האם string המורכב מ-)(][}{ הוא חוקי
תשובות
הוסף תשובה
|
לצפיה בתשובות
ינואר 2017
1. נלך לספר האחרונה במערך נעשה לה -48 שזהו הערך האסקי של 0 נכפייל בעשר בחזק 0 ואז נלך לספרה הבאה ונוריד גם אותה ב48 ונכפיל בעשר בחזק 1 ונוסיף לספרה הקודמת וככה נקבל את הספרה שלנו כאינג'ר ונוכל לעשות חיבור
2. נבנה מחסנית וברגע שנקבל סוגר פותח נכניס אותו למחסנית וברגע שנקבל סוגר נוציא את הראשון מהמחסנית ונבדוק אם זה הסוגר המתאםי אז הצלחנו אחת טיענו
ראיון לתפקיד 
