4.19头条后端面试题

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

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

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

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

快排不能有序，做不了

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++; } } }

你这个输出中1和0的相对顺序不是变了吗

这两个复杂度搞不定的吧

冒泡一轮不就可以了嘛

插入排序吧

明天给你写，今天太晚了

给你个思路吧，快徘的原理

荷兰国旗问题？

Leetcode 75 

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

快排不好保证有序啊