给定一组正整数和负整数，重新排列它，使得一端为正整数，另一端为负整数
我最近遇到了一个软件工程师的Microsoft面试问题。
给定一组正整数和负整数，重新排列它，使得一端为正整数，另一端为负整数， 但保持其原有排列顺序。
例如，给定[1, 7, -5, 9, -12, 15]
答案是： [-5, -12, 1, 7, 9, 15]
这应该在O（n）中完成。
我们可以很容易地在O（n）中做到这一点，但是我不能像在原始数组中那样维护元素的顺序。 如果我们忘记了O（n）的复杂性，有人能告诉我如何在不考虑空间和时间复杂性的前提下保持元素的顺序。
编辑 ：在实际的问题，我们需要有O（1）空间的复杂性也。
为了在恒定的空间（但是二次的时间）中获得这个结果，可以通过在数组的每一端放置一个队列（类似于荷兰国旗algorithm）来使用双队列方法。 从左到右读取项目：将项目添加到左侧队列意味着将项目单独添加，将项目添加到右侧队列意味着将不在队列中的所有元素向左移动一个，并将添加的项目放在最后。 然后，要连接队列，只需颠倒第二个队列中元素的顺序即可。
这将执行O（n）操作（将元素左移）直到O（n）次，这将产生一个O（n²）运行时间。
通过使用类似于合并sorting的方法，可以实现较低的O（n log n）复杂度：将数组分割成两半，recursion地按照[NP] [NP]的forms进行sorting，然后将第一个P与第二个N在O（n）时间（当它们没有完全相同的大小时，它会变得有点棘手，但它仍然是线性的）。
我完全不知道如何把它弄到O（n）的时间。
编辑 ：其实，你的链表洞察是正确的。 如果数据是作为双向链表提供的，则可以在O（n）时间，O（1）空间中实现双队列策略：
sort(list): negative = empty positive = empty while (list != empty) first = pop(list) if (first > 0) append(positive,first) else append(negative,first) return concatenate(negative,positive)
通过链表实现保持指向第一个和最后一个元素的指针，那么pop，append和concatenate都是O（1）操作，所以总的复杂度是O（n）。 至于空间，没有任何操作分配任何内存（追加仅仅使用pop释放的内存），所以总的来说是O（1）。
这里是O（n）时间O（1）空间解的一个构造版本，它假定maxValue *（maxValue + 1）小于Integer.MAX_VALUE，其中maxValue是数组中最大值减最小值的结果。 它利用原始数组作为临时数组来存储结果。
public static void specialSort(int[] A){ int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; for(int i=0; i<A.length; i++){ if(A[i] > max) max = A[i]; if(A[i] < min) min = A[i]; } //Change all values to Positive for(int i=0; i<A.length; i++) A[i]-= min; int newMax = max-min+1; //Save original negative values into new positions int currNegativeIndex = 0; for(int i=0; i<A.length; i++) if(A[i]%newMax < (-min)) A[currNegativeIndex++] += (A[i]%newMax)*newMax; //Save original positive values into new positions int currPositiveIndex = currNegativeIndex; for(int i=0; i<A.length; i++) if(A[i]%newMax > (-min)) A[currPositiveIndex++] += (A[i]%newMax)*newMax; //Recover to original value for(int i=0; i<A.length; i++){ A[i] = A[i]/newMax + min; } }
我不确定我是否正确地理解了这个问题，因为答案似乎太简单了：
- 遍历数组并计算负数 – O（n）
- 创build一个大小为O（n）的新数组
- 遍历原始数组并将数字放入新数组中。 使用已知数量的负数来抵消正数 – O（n）
这是一个在Python中快速完成的方法。 它与上面略有不同，首先为底片创build一个数组，然后添加正数。 所以它不是那么高效，但仍然是O（n）。
>>> a = [1,7,-5,9,-12,15] >>> print [x for x in a if x < 0] + [y for y in a if y >= 0] [-5, -12, 1, 7, 9, 15]
编辑：好吧，现在与O（1）空间的矛盾，它变得更加困难。 我感兴趣的是如何在O（n）时间复杂性上实现它。 如果有帮助，这是一种保持O（1）空间复杂度的方法，但是需要O（n ^ 2）时间复杂度：
- 从最左边的负数开始。 遍历数组，直到find下一个负数。
- 在一个新的循环中，将负数与剩余的正数交换。 做到这一点，直到你到达其他负数。 这确保了号码的顺序保持不变。
- Rince并重复，直到你到达arrays的末尾时，寻找一个新的负数。
它可以在O（n）和空间O（1）中完成。
我们需要通过数组扫描3次，并仔细改变一些值。
假设：大小为N的数组中的最大值应该小于(N+1) * Integer.MAX_VALUE 。
我们需要这个假设，因为我们在数组中改变了一些正值。
- 在第一次扫描中，find负值和正值的数值，
- 在第二次扫描中，我们创build数组的负数部分，如下所示：
我们从数组的开始处开始，将第一个find的正数（例如在索引i ）与第一个find的负数（例如j ）进行“ 交换 ”。 由于负数正在考虑他们的位置，交换将是好的。
问题是正数，因为i和j之间可能还有其他一些正数。 为了处理这个问题，我们必须以某种方式在交换之前对该值中的正数的索引进行编码。 那么我们就可以知道它在哪里。 我们可以通过a[i]=(i+1)*(max)+a[i]来做到这一点。
- 在第三次扫描中，我们创build了数组的正数部分。 在第二次扫描结束时，构造负arrays，正数移到右侧，但是它们的位置可能不正确。 所以我们尽pipe去纠正它们的位置，因为这些信息是编码它们的价值的。
这里是代码：
import java.util.Arrays; public class LinearShifting { public static void main(String[] args) { // TODO Auto-generated method stub int[] a = {-1,7,3,-5,4,-3,1,2}; sort(a); System.out.println(Arrays.toString(a)); //output: [-1, -5, -3, 7, 3, 4, 1, 2] } public static void sort(int[] a){ int pos = 0; int neg = 0; int i,j; int max = Integer.MIN_VALUE; for(i=0; i<a.length; i++){ if(a[i]<0) neg++; else pos++; if(a[i]>max) max = a[i]; } max++; if(neg==0 || pos == 0) return;//already sorted i=0; j=1; while(true){ while(i<=neg && a[i]<0) i++; while(j<a.length && a[j]>=0) j++; if(i>neg || j>=a.length) break; a[i]+= max*(i+1); swap(a,i,j); } i = a.length-1; while(i>=neg){ int div = a[i]/max; if(div == 0) i--; else{ a[i]%=max; swap(a,i,neg+div-2);// minus 2 since a[i]+= max*(i+1); } } } private static void swap(int[] a, int i , int j){ int t = a[i]; a[i] = a[j]; a[j] = t; } }
您可以使用2个队列并合并它们。 这样，你只在第一个数组和一个子队列上迭代一次。
negatives = [] positives = [] for elem in array: if elem >= 0: positives.push(elem) else negatives.push(elem) result = array(negatives, positives)
这是一个只有2次迭代的解决scheme：
假设长度是n。
我将使用C代码，忽略语法错误。
solution[n]; for (i= 0,j=0 ; i < n ; i++ ) { if (array[i] < 0) solution[j++] = array[i]; } for (i = n-1,j=n-1 ; ; i > 0 ; i--) { if (array[i] >= 0) solution[j--] = array[i]; }
这个想法是过一遍，写下我们遇到的所有消极因素。
然后从第二次结束，并从头到尾写下积极的一面。
编辑（5/29/2015）：我忽略了维持外观顺序的要求，所以下面的答案不能满足问题的所有要求。 不过，我原来的回应是为了大家的兴趣。
这是被称为“分区”的一个非常重要的快速sorting子程序的特殊版本。 定义：如果对于0 <= i <p，A [i] <K且对于p <= j <N，A [j]> = K，则具有N个数字条目的数组A被分割为关于索引p处的值K，条目小于K（意思是p = N）或不小于K（意思是p = 0）。 对于有问题的问题，我们将围绕K = 0进行分区。
您可以在O（n）时间内对未分类数组进行分区，使用O（1）附加内存访问数组中的每个条目。 非正式地，你从两端通过数组，移动错误的值。 当在arrays的每一边find一个放错位置的值时，执行交换，然后继续向内步进。 现在的C ++代码：
// Assume array A[] has size N int K = 0; // For particular example partitioning positive and negative numbers int i = 0, j = N-1; // position markers, start at first and last entries while(1) { // Break condition inside loop while(i < N && A[i] < K) i++; // Increase i until A[i] >= K while(j >= 0 && A[j] >= K) j--; // Decrease j until A[j] < K if(i < j) swap(A[i],A[j]); else break; } // A[] is now partitioned, A[0]...A[j] < K, unless i==0 (meaning all entries >= K).
请注意，如果所有元素都等于K（在这种情况下为零），那么i永远不会递增，最后j = 0。 问题陈述假设这不会发生。 分区是非常快速和高效的，这种效率是快速sorting是大型arrays最stream行的sorting程序的原因。 交换function可以在C ++ std :: swap中，或者您可以轻松编写自己的：
void swap(int& a, int& b) { int temp = a; a = b; b = temp; }
或者只是为了好玩，数字可以在没有临时记忆的情况下交换，但要注意溢出：
// This code swaps a and b with no extra space. Watch out for overflow! a -= b; b += a; a = b - a;
对于特殊情况的分区有很多种变化，例如[元素K] [元素K] [元素K]的三分区。 快速sortingalgorithmrecursion地调用分区，并且分区值K通常是当前子数组中的第一个条目或者从几个条目（例如三个中值）计算。 参见教科书：Sedgewick和Wayne的algorithm（第4版，第288页）或计算机编程艺术Vol。 3 Knuth（第二版，第113页）。
该解决scheme具有O（n）时间复杂度和O（1）空间复杂度
想法是：
-
跟踪上次看到的负面元素（lastNegIndex）的索引。
-
循环遍历数组以find正数元素之前的负数元素。
-
如果find这样的元素，则右键在lastNegIndex和当前索引之间旋转一个元素。 然后更新lastNegIndex（它将是下一个索引）。
这里是代码：
public void rightRotate(int[] a, int n, int currentIndex, int lastNegIndex){ int temp = a[currentIndex]; for(int i = currentIndex; i > lastNegIndex+ 1; i--){ a[i] = a[i-1]; } a[lastNegIndex+1] = temp; } public void ReArrange(int[] a, int n){ int lastNegIndex= -1; int index; if(a[0] < 0) lastNegIndex = 0; for(index = 1; index < n; index++){ if (a[index] < 0 && a[index - 1] >= 0) { rightRotate(a, n, index, lastNegIndex); lastNegIndex = lastNegIndex + 1; } } }
如果开始的结构不一定是一个数组，那更简单。
如果你有一个链接列表中的原始数字很容易。
您可以重新安排链接列表，每个时间点负面的下一个否定，下一个正面的积极。
再次C像代码，忽略语法。 （可能需要一个空的检查，但这是这个想法）
Cell firstPositive; Cell* lastPoisitive; lastPoisitive = &firstPositive; Cell firstNegative; Cell* lastNegative; lastNegative = &firstNegative; Cell* iterator; for(Iterator = list.first ; Iterator != null ; Iterator = Iterator->next) { if (Iterator->value > 0 ) lastPoisitive->next = Iterator; else lastPoisitive->next = Iterator; } list.first = firstNegative->next; list.last.next = firstPositive->next;
只是一个想法..让我们考虑一个简单的问题：
给定一个数组，其中第一部分（ Np元素）只包含正数，最后一部分（ Nn元素）：仅包含负数。 如何交换这些部分，而保持相对的顺序呢？
最简单的解决scheme是使用反演：
inverse(array, Np + Nn); // whole array inverse(array, Nn); // first part inverse(array+Nn, Np); // second part
它具有O（n）时间复杂度和O（1）空间复杂度。
如果目标是O（1）空间（除了被假定为可自由变化的元素本身以外）和O（NlgN）时间，则将该问题划分为排列已知为pnPNforms的数组，其中p P代表零个或更多个正数，n和N代表0个或更多个负数，形成pPnNforms的arrays。 任何两个元素的数组将自动成为这种forms。 给定这种forms的两个数组，find第一个负数，下一个正数和最后一个正数，然后“旋转”数组的中间两个部分（易于在恒定的空间内完成，并且时间与数组的大小成正比被“旋转”）。 结果将是一个forms为pPnN的数组。 两个连续的这样的数组将形成更大的formspnPN的数组。
要在恒定的空间中做事，先把所有的元素配对成PNforms。 然后执行所有元素的四元组，然后是所有八位元组，直到数组的总大小。
我非常怀疑O（n）时间和O（1）是否可行。 一些build议链接列表，但你需要一个自定义链接列表，你可以直接访问节点来做到这一点，即。 语言内置的链表不起作用。
这是我的想法，使用一个自定义的双向链表来满足约束的复杂性，以[1，7，-5，9，-12，15]为例：
在列表中循环 ，如果看到否定的，则将其剪下，并将其添加到前面底片的末尾。 每个操作是O（1），所以总的时间是O（n）。 链接列表操作就位，所以O（1）空间。
详细：
last_negative_node = null; at -5: cut off -5 by setting 7.next = 9, then add -5 to front by -5.next = 1, then update last_negative_node = 5 // O(1), the linked list is now [-5, 1, 7, 9, -12, 15] at -12: cut off -12 by setting 9.next = 15, then add -12 to front by -12.next = last_negative_node.next, then update last_negative_node.next = -12, then update last_negative_node = -12 //O(1), the linked list is now [-5, -12, 1, 7, 9, 15] no more negatives so done.
O（n）解决schemeJava
private static void rearrange(int[] arr) { int pos=0,end_pos=-1; for (int i=0;i<=arr.length-1;i++){ end_pos=i; if (arr[i] <=0){ int temp_ptr=end_pos-1; while(end_pos>pos){ int temp = arr[end_pos]; arr[end_pos]=arr[temp_ptr]; arr[temp_ptr]=temp; end_pos--; temp_ptr--; } pos++; } }
我认为这将工作：这是一个简单的方法是恒定的空间（但二次时间）。 假设数组长度为N，从i = 0到i = N-2检查元素i和i + 1。 如果元素i是正数，元素i + 1是负数，则交换它们。 然后重复这个过程。
arrays中的每一次传球都会使得底片向左移动（正向右移），有点类似于气泡排列，直到（经过足够数量的传球之后）他们都处于正确的位置。
此外，我认为这将工作：这也是恒定的空间（但二次时间）。 说P是正数。 从左到右扫描，当您发现一个正的x停止扫描，并通过移动所有的项目后，删除它“删除”。 然后把x放在数组的末尾。 重复步骤扫描P次，移动每一个正数。
首先，计算负数元素的数量k 。 然后，你知道数组的前k数字（数组的第一部分）应该是负数。 对数组进行sorting后，以下N - k元素应该是正数。
你需要维护两个计数器，在这个数组的两个部分中有多less个元素遵守这些条件，并且在每一步中增加它，直到你知道一个部分是正确的（计数器等于那个部分的大小）。 那么另一部分也可以。
这需要O（1）存储并花费O（N）时间。
用C ++实现：
#include <iostream> #include <vector> using namespace std; void swap(vector<int>& L, int i, int j) { int tmp = L[i]; L[i] = L[j]; L[j] = tmp; } void signSort(vector<int>& L) { int cntNeg = 0, i = 0, j = 0; for (vector<int>::iterator it = L.begin(); it < L.end(); ++it) { if (*it < 0) ++cntNeg; } while (i < cntNeg && cntNeg + j < L.size()) { if (L[i] >= 0) { swap(L, i, cntNeg + j); ++j; } else { ++i; } } } int main(int argc, char **argv) { vector<int> L; L.push_back(-1); L.push_back(1); L.push_back(3); L.push_back(-2); L.push_back(2); signSort(L); for (vector<int>::iterator it = L.begin(); it != L.end(); ++it) { cout << *it << endl; } return 0; }
此代码使用O（n）复杂性和O（1）空间。 不需要声明另一个数组。
#include <stdio.h> int* sort(int arr[], int size) { int i; int countNeg = 0; int pos = 0; int neg = 0; for (i = 0; i < size; i++) { if (arr[i] < 0) pos++; } while ((pos < (size-1)) || (neg < size-(pos-1))) { if ((arr[pos] < 0) && (arr[neg] > 0)) { arr[pos] = arr[pos] + arr[neg]; arr[neg] = arr[pos] - arr[neg]; arr[pos] = arr[pos] - arr[neg]; pos++; neg++; continue; } if ((arr[pos] < 0) && (arr[neg] < 0)) { neg++; continue; } if ((arr[pos] > 0) && (arr[neg] > 0)) { pos++; continue; } if ((arr[pos] > 0) && (arr[neg] < 0)) { pos++; neg++; continue; } } return arr; } void main() { int arr[] = { 1, 7, -5, 9, -12, 15 }; int size = sizeof(arr) / sizeof(arr[0]); sort(arr, size); int i; for (i = 0; i < size; i++) { printf("%d ,", arr[i]); } printf(" \n\n"); }
#include <iostream> using namespace std; void negativeFirst_advanced (int arr[ ], int size) { int count1 =0, count2 =0; while(count2<size && count1<size) { if(arr[count1]>0 && arr[count2]<0) { int temp = arr[count1]; arr[count1] = arr[count2]; arr[count2] = temp; } if (arr[count1]<0) count1++; if (arr [count2]>0) count2++; } } int main() { int arr[6] = {1,7,-5,9,-12,15}; negativeFirst_advanced (arr, 6); cout<<"["; for (int i =0; i<6;i++) cout<<arr[i]<<" , "; cout<<"]"; system("pause"); return 0; }
这里是我在Python中的解决scheme，使用recursion（我有一个像这样的任务，其中数组应该相对于数字Ksorting。如果你把K = 0，你有你的解决scheme， 没有保留外观的顺序 ） ：
def kPart(s, k): if len(s) == 1: return s else: if s[0] > k: return kPart(s[1:], k) + [s[0]] else: return [s[0]] + kPart(s[1:], k)
这不是复杂性O（1），而是一个更简单的方法。 做评论
void divide (int *arr, int len) { int positive_entry_seen = 0; for (int j = 0; j < len ; j++) { if (arr[j] >= 0 ) { positive_entry_seen = 1; } else if ((arr[j] < 0 ) && positive_entry_seen) { int t = arr[j]; int c = j; while ((c >= 1) && (arr[c-1] >= 0)) { arr[c] = arr[c-1]; c--; } arr[c] = t; } } }
一个非常简单的解决scheme在下面，但不在O（n）中。 我改变了一下插入sortingalgorithm。 而不是检查一个数字是更大还是更小，它检查它们是大于还是小于零。
int main() { int arr[] = {1,-2,3,4,-5,1,-9,2}; int j,temp,size; size = 8; for (int i = 0; i <size ; i++){ j = i; //Positive left, negative right //To get opposite, change it to: (arr[j] < 0) && (arr[j-1] > 0) while ((j > 0) && (arr[j] >0) && (arr[j-1] < 0)){ temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; j--; } } //Printing for(int i=0;i<size;i++){ cout<<arr[i]<<" "; } return 0; }
以下是qiwangcs解决scheme的JavaScript实现：
function specialSort(A){ let min = Number.MAX_SAFE_INTEGER, max = -Number.MAX_SAFE_INTEGER; for(let i=0; i<A.length; i++){ if(A[i] > max) max = A[i]; if(A[i] < min) min = A[i]; } //Change all values to Positive for(let i=0; i<A.length; i++) A[i]-= min; const newMax = max-min+1; //Save original negative values into new positions let currNegativeIndex = 0; for(let i=0; i<A.length; i++) if(A[i]%newMax < (-min)) A[currNegativeIndex++] += (A[i]%newMax)*newMax; //Save original positive values into new positions let currPositiveIndex = currNegativeIndex; for(let i=0; i<A.length; i++) if(A[i]%newMax > (-min)) A[currPositiveIndex++] += (A[i]%newMax)*newMax; //Recover to original value for(let i=0; i<A.length; i++){ A[i] = Math.floor(A[i]/newMax) + min; } } // Demo const A = [-3,-7,2,8,-5,-2,4]; specialSort(A); console.log(A);
这可以简单地通过O（n）中的步骤来完成，而不使用任何额外的空间
int count = 0; //data is the array/vector in sort container having given input. if(data[0] < 0) count++; for(int i = 1; i < n; i++) { if(data[i] < 0) { int j = i; while(j> count) { data[j-1] += data[j]; data[j] = (data[j-1]-data[j]); data[j-1] -= data[j]; j--; } count++; } }
它的完整实现可以在这里findhttps://gist.github.com/Shravan40/8659568
我已经硬编码数组的值。 然而，它将工作任何整数集。
int[] n={2,-3,1,5,-10,-8}; int k=0; for(int i=1;i<n.length;i++) { int temp=0; if(n[i]<0) { temp=n[k]; n[k]=n[i]; n[i]=temp; k++; } } for(int j=0;j<n.length;j++) { System.out.println(n[j]); }
我希望这有帮助。 这个有时间复杂度O（n ^ 2）
#include <stdio.h> int main() { int a[] = {-3, 2, -5, 9, -2, -8, 6, 8, -1, 6}; int length = (sizeof(a) / sizeof(int)); int i, j = 0; printf("Size of array: %d\n", sizeof(a)); for (i = 0; i < length; i++) { if (i % 2 == 0 && a[i] < 0) { for (j = i + 1; j < length; j++) { if (a[j] > 0) { int t = a[i]; a[i] = a[j]; a[j] = t; break; } } } else if (i % 2 == 1 && a[i] > 0) { for (j = i + 1; j < length; j++) { if (a[j] < 0) { int t = a[i]; a[i] = a[j]; a[j] = t; break; } } } } for (i = 0; i < length; i++) { printf("Value at %d: %d\n", i, a[i]); } return 0; }
编辑1这依靠的事实，大于零的数字总是在一个偶数索引和小于零的数字总是在奇数索引
编辑2改进了一些代码
这里我的答案是在单个数组中的两个单独的正值和负值，它会帮助你
int[] singleArray= {300, -310, 320, 340, 350, -330, 420, 370, -360, 390, 340, -430, 320, -463, 450}; public double[] getPositive_SingleArray() { double minValue = 0; double positiveValue=0; int count=0; for (int i = 0; i < singleArrayData.length; i++) { if ( singleArrayData[i]>0) count++; } positiveSingleArrayData=new double[count]; int k=0; for (int i = 0; i < singleArrayData.length; i++) { if ( singleArrayData[i]>0){ positiveSingleArrayData[k] = singleArrayData[i]; k++; } } System.out.println("single array of positve values "+Arrays.toString(positiveSingleArrayData)); return positiveSingleArrayData; }
我已经尝试过使用气泡sorting方法，它完美的工作，并保持其在原始数组中的外观顺序。
int main() { int array[TAM], num, i=0, j=0; printf("Ingrese arreglo: "); for(i=0; i < TAM -1 && num != 0; i++) { scanf("%d", &num); array[i]=num; } for(i=0; array[i] != 0 ; i++) { j++; } Alternar(array, j); //MOSTRAR for(i=0; i < j; i++) { printf("%d ", array[i]); } return 0; } void Alternar(int array[], int j) { int i=0, aux, pasadas=1; for(pasadas=1; pasadas < j; pasadas++) { for(i=0; i < j - pasadas ; i++) { if(array[i] > 0 && array[i+1] < 0) { aux = array[i]; array[i] = array[i+1]; array[i+1] = aux; } } } }
查看维基百科sortingalgorithm表中的Heapsort： http ： //en.wikipedia.org/wiki/Sorting_algorithm
