两边夹的应用二

2020 年 04 月 22 日 阅读数: 14
两边夹的应用二

上篇写到两边夹的思路应用场景应该是比较多的,所以就又特地找了一个题目来扩展这个话题,顺便用一用自定义Lambda表达式。

举例,给定一个数组,要求对数组重新排序,奇数在前,偶数在后。这个问题就很适合继续用两边夹的方式来处理。总体思路上是从左边遍历找到第一个偶数,从右边遍历找到第一个奇数,如果左边找到的位置小于右边找到的位置,交换两个位置上的数,然后各自从当前位置继续重复如上动作,可以画个图来说明。

用黄色箭头表示从左遍历的下标变化情况,红色箭头表示从右遍历的下标变化 情况,碰到符合条件的数时,进行交换操作。

分析了主体思路后,我们要考虑一些边界条件,如果数组为空或元素少于2个,则没必要执行重排。还有另外两种极端情况,当数组全为奇数或全为偶数时,下标一直碰不到符合条件的数,如果不做边界判断会出现越界情况。经过如上分析后,完成代码的具体实现如下:

public void reorderByOddEven(int[] ints) {
if (ints == null || ints.length < 2) {
return;
}
for (int left = 0, right = ints.length - 1; left < right; ) {
while (left < ints.length && (ints[left] & 1) == 1) {
left++;
}
while (right >= 0 && (ints[right] & 1) == 0) {
right--;
}
if (left < right) {
swap(ints, left, right);
}
}
}
privat void swap(int[] ints, int left, int right) {
int temp = ints[right];
ints[right] = ints[left];
ints[left] = temp;
}

这里对于while中的判定条件也可以采用另一种方式,这种方式会更早的使程序在全奇或全偶的极端下退出执行。如下:

while ((ints[left] & 1) == 1) {
left++;
if (left >= ints.length) {
break;
}
}
while ((ints[right] & 1) == 0) {
right--;
if (right < 0) {
break;
}
}

但是简洁性上还是第一种要好些。

接下来仍然从这个问题展开,来应用Java中的Lambda表达式。现在我们假设针对类似重新排序的需求多种多样,除了要按照奇偶重排,还可能会按某个阈值重新排列,或者按照能否被3整除重新排列,又可能按是否大于0来排列,等等,这种情况下,如果我们要实现多个重排函数,发现只是判定条件不一样,那就很难具有通用性,这时候我们可以借鉴JDK排序时用的比较器的实现方式,既然只是判定方法不一样,那可以让重排函数接受一个判定函数作为参数。接下来看具体实现。

先定义一个函数式接口如下:

@FunctionalInterface
public interface ReorderCondition {
boolean check(int num);
}

该接口定义一个方法,用来判定给定的整数是否符合条件。接下来将重排函数改造如下:

private void reorderByCondition(int[] ints, ReorderCondition reorderCondition) {
if (ints == null || ints.length < 2) {
return;
}
for (int left = 0, right = ints.length - 1; left < right; ) {
while (left < ints.length && reorderCondition.check(ints[left])) {
left++;
}
while (right >= 0 && !reorderCondition.check(ints[right])) {
right--;
}
if (left < right) {
swap(ints, left, right);
}
}
}

相应的在使用时以如下方式调用,仍然以奇偶重排为例:

reorderByCondition(ints, num -> {
return (num & 1) == 1;
});
//或者为了条件可以重用,先定义再引用
ReorderCondition oddEven = num -> {
return (num & 1) == 1;
};
reorderByCondition(ints, oddEven);

同理我们可以实现以是否能被3整除重排,如下:

reorderByCondition(ints, num -> {
return (num % 3) == 0;
});

等等。

对于函数式接口进一步做个说明,标注不是必须的,但是函数式接口有个条件,就是有且只有一个抽象函数,所以为了让该接口更清晰,不被当作普通接口使用,加上标注会更合适,这样当你在函数式接口中定义了超过一个抽象函数或者都是带有实现的default方法时编译器会报错,尽可能避免使用上的混淆。

相关主题:

两边夹的应用

用户头像

孙苏勇

关注

不读书,思想就会停止。 2018.04.05 加入

公众号“像什么",记录想记录的。

评论

发布
暂无评论
两边夹的应用二