axg
BAN USERI don't think you need 2 rounds for odd. In both cases (even or odd n), instead of incrementing i by 2, increment it by 1 and ensure the odd place number is greater than even.
for(int i = 1; i < n; ++i) {
if (((i & 1) && nums[i] < nums[i-1]) || (!(i & 1) && nums[i] > nums[i-1])) {
swap(nums[i], nums[i-1]);
}
}
Note this only works if there are no duplicates. For example if arr = [1,2,2,3], The answer is [2,3,1,2] which won't be achieved by the above.
- axg May 17, 2017Assuming no cyclic ownership exists.
1. Topological sort the graph (from source company to destination company)
2. Now in the topological order calculate ownership as follows
own[B] += own[A] * weight(A, B)/100;
3. return own[C]
Time complexity O(|V| + |E|)
Space Complexity: O(|V|)
1. Sort the numbers
2. Reverse the second half (i.e. if n is odd reverse last n/2 + 1 numbers). For example: if
sorted nums = {1,2,3,4,5} after reversal nums = {1,2,5,4,3}
3. Keep 2 pointers i = 0 and j = n-1 (if n is even) or n-2 if (n is odd). In odd case after reversal the last number is at its final position so we start from n-2
4. Keep 2 temporary variables (temp_i and temp_j). These variables will store the elements originally in the locations being updated
5. Now do the following:
#define A(i) nums[(1 + 2*(i)) % (n | 1)]
int i = 0;
int j = n - (1 + n%2); // for even and odd as explained above
int temp_i = nums[i];
int temp_j = nums[j];
int cnt = 0;
while(cnt < n/2) {
/* places nums stored in temp_i, temp_j in their final position and loads the numbers currently in those locations into these temp vars for next round */
swap(A(i), temp_i);
swap(A(j), temp_j);
i = (1 + 2*(i)) % (n | 1);
j = (1 + 2*(j)) % (n | 1);
cnt++;
}
Thus, O(nlogn) time complexity and O(1) space. This is similar to wiggly sort.
- axg April 18, 2017Instead of find_loc() being O(n) (in number of workers), you can maintain a min priority_queue to find the minimum loaded worker in O(1). Remove this from queue, update its time and re-insert (O(log(n))
Overall then the algo becomes O(mlog(n)) with n workers and m tasks.
Its a variation of word break problem. Solve it via DP. Time complexity: O(n^3)
spaces[i] : minimum spaces achieved for string ending at i. Then,
Based on the min k you can set the parent location to find the best break point in the string.
- axg July 25, 2017