4.19头条后端面试题

如果能做到这样那快排不就可以做到O(nlogn)且保持稳定性吗

先扫一遍找出0或者离0最近的数O(n)，作为基准，然后只跑一轮快排O(n)，结束

mark，这题整出来，坑人的吧

public void sort(int[] nums){ int len = nums.length; int first = 0; int last = len; int mid = 0; while(mid<last){ if(nums[mid]<0){ if (mid==first){ mid++; first++; continue; } int i = mid; int tmp = nums[mid]; while(i>first){ nums[i]= nums[i-1]; i--; } nums[first] = tmp; first++; } else if(nums[mid]>0){ int i = mid; int tmp = nums[mid]; while(i<len-1){ nums[i] = nums[i+1]; i++; } nums[len-1]=tmp; last--; } else{ mid++; } } }

快排不能有序，做不了

既要稳定性又要O（n）和O（1），左神不是说目前还是实现不了吗🤔

def reOrderArray(L):     if not L:         return L     i, N = 0, len(L)     while i < N:         while i < N and L[i] < 0:             i += 1         j = i + 1         while j < N and L[j] > 0:             j += 1         if j < N:             L[i], L[i+1:j+1] = L[j], L[i:j]         else:             break     return L

打印一份0-1 stablesort的paper拍在面试官脸上

先遍历一遍数组，记录正数个数和负数个数，然后再从头遍历，调整位置。

等一个答案

只能从稳定排序里挑吧，冒泡或者插入？但是要O(N)好像有点难

跑一次快排的partition就行了

做不了……

快排不好保证有序啊

m

void func(vector& arr) { int m = 0, n, p = arr.size()-1, q; for (int i = 0; i < arr.size(); ++i) { if (arr[i] < 0) { n = i; while (i > m) { swap(arr[i--], arr[i]); } m++; i = n; } } for (int i = arr.size()-1; i >=0;--i) { if (arr[i] > 0) { q = i; while (i < p) { swap(arr[i++], arr[i]); } p--; i = q; } } }

同向双指针遍历一遍即可

剑指原题稍微变了一下，，

m

Leetcode 75