t**r
发帖数: 3428 | 1 google-interview-questions
0
of 0 votes
10
Answers
Given an array Of integers build a new array of integers such that every 2nd
element of the array is greater than its left and right element.
eg:
[1,4,5,2,3]
o/p:
[1,4,2,5,3]
so, 3 > 2 > 1, and 5 > 4
有没有o(n) 解法 | k****p
发帖数: 9 | 2 用quick sort的partition方法找最小的(n+1)/2数, random种子，O(n)吧。
然后把这(n+1)/2放在偶数坐标，剩下放奇数坐标。O(n) space或in place都行。
2nd
【在 t**r 的大作中提到】
: google-interview-questions
: 0
: of 0 votes
: 10
: Answers
: Given an array Of integers build a new array of integers such that every 2nd
: element of the array is greater than its left and right element.
: eg:
: [1,4,5,2,3]
: o/p:
| t********5
发帖数: 522 | 3 好像是cc150还是lc原题吧
记得有o(n)解 走一遍把不符合条件的左右swap就好了 忘记题目叫什么了 。。。
if less:
if a[left] > a[right]:
a[left], a[right] = a[right], a[left]
less = False
else:
if a[right] < a[left]:
a[left], a[right] = a[right], a[left]
less = True | t**r
发帖数: 3428 | 4 你题目没完全理解。
【在 t********5 的大作中提到】
: 好像是cc150还是lc原题吧
: 记得有o(n)解 走一遍把不符合条件的左右swap就好了 忘记题目叫什么了 。。。
: if less:
: if a[left] > a[right]:
: a[left], a[right] = a[right], a[left]
: less = False
: else:
: if a[right] < a[left]:
: a[left], a[right] = a[right], a[left]
: less = True
| i*********7
发帖数: 348 | 5 这个好像不是很难吧？
for(int i = 0; i < arr.length; i += 2){
int index = findMaxIndex(arr, i, i + 1, i + 2);
if(index != i + 1)
swap(arr[i + 1], arr[index]);
}
这样不就好了么？ | y******g
发帖数: 4 | 6 #include
#include
using namespace std;
void print(const vector &A) {
int count = 0;
cout << "[";
for(auto &i : A) {
if (count++) {
cout << ", ";
}
cout << i;
}
cout << "]" << endl;
};
void zigzag(vector &A) {
if (A.empty()) return;
for (size_t i = 1; i < A.size(); ++i) {
if (i&0x01) { // odd position element should be a local maximum
if (A[i] <= A[i-1]) {
swap(A[i-1], A[i]);
}
} else { // even position element should be a local minimum
if (A[i] > A[i-1]) {
swap(A[i-1], A[i]);
}
}
}
};
int main() {
// your code goes here
vector a1{1, 4, 5, 2, 3};
cout << "Before: ";
print(a1);
zigzag(a1);
cout << "After: ";
print(a1);
return 0;
} | i****7
发帖数: 26 | | l***i
发帖数: 1309 | 8 kkkppp already gave a solution.
A special case is to put the top n/2 elements in even position and bottom n/
2 elements in odd position, 1-based index. Now the problem reduces to find
median of this array, which can be done in worse case O(n) time using median
of median's algorithm, almost every algorithm book has the algorithm. | e**y
发帖数: 784 | 9 直接从左到右扫行不行，求指正
假设A[0], A[1], ... A[i-1] 已经sort好
A[i-1] A[i] A[i+1] 值顺序m1
分配A[i-1]=m1, A[i]=m3, A[i+1]=m2
用这种分配方式，在保证A[i]>A[i-1], A[i]>A[i+1]的同时，仍然保证A[i-1]
然后继续处理 A[i+1] A[i+2] A[i+3]，以此类推
这种思路有错吗？还是我理解题目有问题？ | r**h
发帖数: 1288 | 10 直接swap就可以了呀
随机generate了500个test case，没有问题
import random
def ShouldSwap(test_case, i):
if i % 2 == 0 and test_case[i] > test_case[i+1]:
return True
elif i % 2 == 1 and test_case[i] < test_case[i+1]:
return True
else:
return False
def Validate(test_case):
i = 0
while i < len(test_case) - 1:
if ShouldSwap(test_case, i):
return False
i = i + 1
return True
def FuzzySort(test_case):
i = 0
while i < len(test_case) - 1:
if ShouldSwap(test_case, i):
test_case[i], test_case[i+1] = test_case[i+1], test_case[i]
i = i + 1
def Process(num_of_cases):
N = 0
while N < num_of_cases:
size = int(random.uniform(2, 20))
test_case = [int(random.uniform(1, 100)) for i in range(0, size)]
print(test_case)
FuzzySort(test_case)
print(test_case)
print(Validate(test_case))
N = N + 1
if __name__ == '__main__':
num_of_cases = 500
Process(num_of_cases) | | | e**y
发帖数: 784 | 11 直接从左到右扫行不行，求指正
假设A[0], A[1], ... A[i-1] 已经sort好
A[i-1] A[i] A[i+1] 值顺序m1
分配A[i-1]=m1, A[i]=m3, A[i+1]=m2
用这种分配方式，在保证A[i]>A[i-1], A[i]>A[i+1]的同时，仍然保证A[i-1]
然后继续处理 A[i+1] A[i+2] A[i+3]，以此类推
这种思路有错吗？还是我理解题目有问题？ | i*********7
发帖数: 348 | 12 我的想法和你的是一样的，我觉得这一题没有那么复杂
【在 e**y 的大作中提到】
: 直接从左到右扫行不行，求指正
: 假设A[0], A[1], ... A[i-1] 已经sort好
: A[i-1] A[i] A[i+1] 值顺序m1: 分配A[i-1]=m1, A[i]=m3, A[i+1]=m2
: 用这种分配方式，在保证A[i]>A[i-1], A[i]>A[i+1]的同时，仍然保证A[i-1]: 然后继续处理 A[i+1] A[i+2] A[i+3]，以此类推
: 这种思路有错吗？还是我理解题目有问题？
| l*****n
发帖数: 246 | 13 我也觉得从左到右扫一遍就行了
【在 i*********7 的大作中提到】
: 我的想法和你的是一样的，我觉得这一题没有那么复杂
| e********u
发帖数: 587 | 14 排个序不就是NlogN了么...
【在 e**y 的大作中提到】
: 直接从左到右扫行不行，求指正
: 假设A[0], A[1], ... A[i-1] 已经sort好
: A[i-1] A[i] A[i+1] 值顺序m1: 分配A[i-1]=m1, A[i]=m3, A[i+1]=m2
: 用这种分配方式，在保证A[i]>A[i-1], A[i]>A[i+1]的同时，仍然保证A[i-1]: 然后继续处理 A[i+1] A[i+2] A[i+3]，以此类推
: 这种思路有错吗？还是我理解题目有问题？
| k****p
发帖数: 9 | 15 恩，想复杂了，就当发散下思路~
【在 i*********7 的大作中提到】
: 我的想法和你的是一样的，我觉得这一题没有那么复杂
| q****o
发帖数: 6 | 16 感觉没问题，即便m1要放到中间，也是对的。
【在 i*********7 的大作中提到】
: 我的想法和你的是一样的，我觉得这一题没有那么复杂
| Q**F
发帖数: 995 | 17 如果m1=m2=m3怎么处理？
【在 e**y 的大作中提到】
: 直接从左到右扫行不行，求指正
: 假设A[0], A[1], ... A[i-1] 已经sort好
: A[i-1] A[i] A[i+1] 值顺序m1: 分配A[i-1]=m1, A[i]=m3, A[i+1]=m2
: 用这种分配方式，在保证A[i]>A[i-1], A[i]>A[i+1]的同时，仍然保证A[i-1]: 然后继续处理 A[i+1] A[i+2] A[i+3]，以此类推
: 这种思路有错吗？还是我理解题目有问题？
| Q**F
发帖数: 995 | 18
【在 e**y 的大作中提到】
: 直接从左到右扫行不行，求指正
: 假设A[0], A[1], ... A[i-1] 已经sort好
: A[i-1] A[i] A[i+1] 值顺序m1: 分配A[i-1]=m1, A[i]=m3, A[i+1]=m2
: 用这种分配方式，在保证A[i]>A[i-1], A[i]>A[i+1]的同时，仍然保证A[i-1]: 然后继续处理 A[i+1] A[i+2] A[i+3]，以此类推
: 这种思路有错吗？还是我理解题目有问题？
| C*********r
发帖数: 21 | 19 how about this?
1. O(n) to find the median value of the array.
2. split the array to A{a1, a2, ....} > median, and B{b1, b2, ....} < median
3. insert b1 between a1, a2 using a separate array
any value in B > A, so any value in b will be bigger than a1, a2, ... | c*****e
发帖数: 3226 | 20 void wiggleSort(int a[]) {
if (a == null || a.length <=1) return;
boolean oddPos = true;
int i=0;
while(i <= a.length-2) {
if ((oddPos && a[i] > a[i+1]) ||
(!oddPos && a[i] < a[i+1])) {
int t = a[i+1];
a[i+1] = a[i];
a[i] = t;
}
i++;
oddPos = !oddPos;
}
}
【在 e**y 的大作中提到】
: 直接从左到右扫行不行，求指正
: 假设A[0], A[1], ... A[i-1] 已经sort好
: A[i-1] A[i] A[i+1] 值顺序m1: 分配A[i-1]=m1, A[i]=m3, A[i+1]=m2
: 用这种分配方式，在保证A[i]>A[i-1], A[i]>A[i+1]的同时，仍然保证A[i-1]: 然后继续处理 A[i+1] A[i+2] A[i+3]，以此类推
: 这种思路有错吗？还是我理解题目有问题？
| e**y
发帖数: 784 | 21 没排序。。。
我说的sort好是假设已经做到第i步
【在 e********u 的大作中提到】
: 排个序不就是NlogN了么...
| w*****d
发帖数: 105 | 22 From your statement, it seems all the odd and even position elements in the
output array are both sorted, so I think there is no O(N) solutions.
The best way I can figure out is sort the array first(O(NlogN)), and then do
O(N) swaps in one pass:
1 2 3 4 5 6 7 ...
to
1 3 2 5 4 7 6 ... |
|
