h****p
发帖数: 87 | 1 忘了是在哪看到的了 今天突然想起来。。。
题目： a1a2a3b1b2b3 排序成 a1b1a2b2a3b3
大家有什么好思路？ | h****p
发帖数: 87 | 2 PS：避免歧义 大致的意思就是根据字母后一位的数字排序 | r**h
发帖数: 1288 | 3 自定义compare函数然后直接排序就行了吧？
【在 h****p 的大作中提到】
: 忘了是在哪看到的了 今天突然想起来。。。
: 题目： a1a2a3b1b2b3 排序成 a1b1a2b2a3b3
: 大家有什么好思路？
| g*******s
发帖数: 2963 | 4 First swap elements in the middle pair
Next swap elements in the middle two pairs
Next swap elements in the middle three pairs
iterate n-1 steps.
Ex: with n = 4.
a1 a2 a3 a4 b1 b2 b3 b4
a1 a2 a3 b1 a4 b2 b3 b4
a1 a2 b1 a3 b2 a4 b3 b4
a1 b1 a2 b2 a3 b3 a4 b4
不过这个貌似O(n^2)..... | p*****2
发帖数: 21240 | 5
comparator怎么写？
【在 r**h 的大作中提到】
: 自定义compare函数然后直接排序就行了吧？
| P***t
发帖数: 1006 | 6 我觉得可以这样：
#pragma pack(push, 1)
struct TwoChar {
char c1, c2;
};
#prgam pop
bool operator < (const TwoChar& p1, const TwoChar& p2) {
return p1.c2 == p2.c2 ? (p1.c1 < p2.c1)
: (p1.c2 < p2.c2);
}
void StrangeSort(char* s) {
TwoChar* p = (TwoChar*)s;
stl::sort(p, p + strlen(s) / 2);
}
【在 p*****2 的大作中提到】
:
: comparator怎么写？
| e*******o
发帖数: 4654 | 7 perl:
$ join '', sort {(reverse $a) cmp (reverse $b) } "a1a2a3b1b2b3" =~ /../g
a1b1a2b2a3b3 | s*******s
发帖数: 1031 | 8 ////////////////////////////////////////////////////////////////////////
// Note: it is O(n) time, O(1) space, use tree can verify. ////////////
// http://blog.csdn.net/qq675927952/article/details/6326525 ////////////
////////////////////////////////////////////////////////////////////////
#include
using namespace std;
/*
输入a1,a2,...,an,b1,b2,...,bn, 在O(n)的时间,O(1)的空间将这个序列顺序改为a1,
b1,a2,b2,a3,b3,...,an,bn，且不需要移动，通过交换完成，只需一个交换空间。
一
a1a2a3a4 b1b2b3b4
a1a2b1b2 a3a4b3b4
二
a1a2a3a4a5 b1b2b3b4b5
a1a2b1b2b3 a3a4a5b4b5
a1a2b1b2a3 b3a4a5b4b5
*/
void solve(int arr[],int s ,int e)
{
if( s >= e)
return;
int center = (s+e)/2;
//left part: s,...,center;
//right part center+1,...,e
int ls = s;
int le = center;
int rs = center+1;
int re = e;
for(int i=(le+ls)/2+1,j = rs ; i <= le; i++,j++)
mySwap(arr[i],arr[j]);
//奇数个
if(le!=ls && (le-ls)%2==0){
le++;
rs--;
}
solve(arr,ls,le);
solve(arr,rs,re);
} | h****p
发帖数: 87 | 9 good！thx man
【在 s*******s 的大作中提到】
: ////////////////////////////////////////////////////////////////////////
: // Note: it is O(n) time, O(1) space, use tree can verify. ////////////
: // http://blog.csdn.net/qq675927952/article/details/6326525 ////////////
: ////////////////////////////////////////////////////////////////////////
: #include
: using namespace std;
: /*
: 输入a1,a2,...,an,b1,b2,...,bn, 在O(n)的时间,O(1)的空间将这个序列顺序改为a1,
: b1,a2,b2,a3,b3,...,an,bn，且不需要移动，通过交换完成，只需一个交换空间。
:
| w********p
发帖数: 948 | | | | r*********n
发帖数: 4553 | 11 Isn't it O(nlogn) ?
T(n) = 2*T(n/2) + n/2
【在 s*******s 的大作中提到】
: ////////////////////////////////////////////////////////////////////////
: // Note: it is O(n) time, O(1) space, use tree can verify. ////////////
: // http://blog.csdn.net/qq675927952/article/details/6326525 ////////////
: ////////////////////////////////////////////////////////////////////////
: #include
: using namespace std;
: /*
: 输入a1,a2,...,an,b1,b2,...,bn, 在O(n)的时间,O(1)的空间将这个序列顺序改为a1,
: b1,a2,b2,a3,b3,...,an,bn，且不需要移动，通过交换完成，只需一个交换空间。
:
| s*********s
发帖数: 318 | 12 http://tiny/1fpew40ab/stacques5347howt
好像也没有明确答案。
我save了一份答案，号称O（N），不知道对不对？
#include "stdio.h"
//轮换
void Cycle(int Data[], int Length, int Start) {
int Cur_index, Temp1, Temp2;
Cur_index = (Start * 2) % (Length + 1);
Temp1 = Data[Cur_index - 1];
Data[Cur_index - 1] = Data[Start - 1];
while (Cur_index != Start) {
Temp2 = Data[(Cur_index * 2) % (Length + 1) - 1];
Data[(Cur_index * 2) % (Length + 1) - 1] = Temp1;
Temp1 = Temp2;
Cur_index = (Cur_index * 2) % (Length + 1);
}
}
//数组循环移位 参考编程珠玑
void Reverse(int Data[], int Len) {
int i, Temp;
for (i = 0; i < Len / 2; i++) {
Temp = Data[i];
Data[i] = Data[Len - i - 1];
Data[Len - i - 1] = Temp;
}
}
void ShiftN(int Data[], int Len, int N) {
Reverse(Data, Len - N);
Reverse(&Data[Len - N], N);
Reverse(Data, Len);
}
//满足Lenth=3^k-1的perfect shuffle的实现
void Perfect1(int Data[], int Lenth) {
int i = 1;
if (Lenth == 2) {
i = Data[Lenth - 1];
Data[Lenth - 1] = Data[Lenth - 2];
Data[Lenth - 2] = i;
return;
}
while (i < Lenth) {
Cycle(Data, Lenth, i);
i = i * 3;
}
}
//查找最接近N的3^k
int LookUp(int N) {
int i = 3;
while (i <= N + 1) i *= 3;
if (i > 3) i = i / 3;
return i;
}
void perfect(int Data[], int Lenth) {
int i, startPos = 0;
while (startPos < Lenth) {
i = LookUp(Lenth - startPos);
ShiftN(&Data[startPos + (i - 1) / 2], (Lenth - startPos
) / 2, (i - 1) / 2);
Perfect1(&Data[startPos], i - 1);
startPos += (i - 1);
}
}
#define N 100
void main() {
int data[N] = {0};
int i = 0;
int n;
printf("please input the number of data you wanna to test
(should less than 100):\n");
scanf("%d", &n);
if (n & 1) {
printf("sorry,the number should
be even ");
return;
}
for (i = 0; i < n; i++)
data[i] = i + 1;
perfect(data, n);
for (i = 0; i < n; i++)
printf("%d ", data[i]);
} | d****n
发帖数: 233 | 13 void Swap(int[] A, int left, int right)
{
if (A[left] != A[right])
{
A[left] ^= A[right];
A[right] ^= A[left];
A[left] ^= A[right];
}
}
int FindIndex(int current, int N)
{
return (current % 2) * N + current / 2;
}
void solve2(int[] arr)
{
int Len = arr.Length / 2;
for (int i = 0; i < arr.Length; ++i)
{
int index = FindIndex(i, Len);
while (index < i)
{
index = FindIndex(index, Len);
}
Swap(arr, i, index);
}
} | s*********s
发帖数: 318 | 14 zan! 简化多了!
【在 d****n 的大作中提到】
: void Swap(int[] A, int left, int right)
: {
: if (A[left] != A[right])
: {
: A[left] ^= A[right];
: A[right] ^= A[left];
: A[left] ^= A[right];
: }
: }
: int FindIndex(int current, int N)
| s*******u
发帖数: 220 | 15 faster/slow pointer,一个跑到end,一个刚好跑到中间,然后再处理.
【在 h****p 的大作中提到】
: 忘了是在哪看到的了 今天突然想起来。。。
: 题目： a1a2a3b1b2b3 排序成 a1b1a2b2a3b3
: 大家有什么好思路？
| m*****o
发帖数: 70 | |
|
