当前位置: 代码迷 >> 综合 >> 剑指offer之数组划分
  详细解决方案

剑指offer之数组划分

热度:16   发布时间:2024-01-16 23:51:01.0

1.数组划分O(n)复杂度

按照一定规则,划分数组,使得满足规则的元素排列在数组前段,不满足规则的排列在后段

  • 比如奇数排在偶数前,那么规则就是n&1==1

  • 比如负数排在非负数前,那么规则就是n<0

  • 代码不难,难在扩展性思路,规则可以随意变化,代码主体不变

2.代码

bool rule_func(int n)
{//规则函数,满足规则的排在前面return n&1 == 1;//n是奇数,表示奇数在前面//return n % 3 == 0;//n是3的倍数,表示3的倍数排在前面
}void partion(int* p, unsigned int length, bool (*rule_func)(int))
{if(p==NULL || length<=0)return;int* begin = p;int* end = p + length - 1;while(begin < end){while(begin < end && rule_func(*begin))//满足规则,往后移,找到一个不满足规则(想要在后面去)的begin ++;while(begin < end && !rule_func(*end))//不满足规则,往前移,找到第一个满足规则(想要在前面去)的end --;if(begin < end){int temp = *begin;*begin = *end;*end = temp;}}
}
  相关解决方案