如何按照升序排序一个数组（int left，int right），但是如果left（i）= left（i + 1）将其排序到右（i）和右（i + 1） [英] How to sort an array of segments (int left, int right) in a ascending order but if left(i)=left(i+1) sort it acording to right(i) and right(i+1)
问题描述
我有一个类Segment和一个这样的段数组：
private static class段{
int数字，类型;
段（int number，int type）{
this.number = number;
this.type = type;
}
}
段[] points = new Segment [n];
points = {（0，-1），（1,0），（5,1），（6,0），（6，-1），（10,1），（11,0） }
左边的元素是一个点列表，右边的列表是类型的点：-1打开一个段，1个关闭一个段，0个与该段相交。
如你所见，这个数组已经按照编号进行排序，使用这个代码（它是一个改编的selectionSort）：
maxI找到最大的索引number元素
private static int maxI（Segment [] segments，int size）{
int max = 0 ; （int i = 0; i< size; i ++）{
if（segments [i] .number> segments [max] .number）{
max = i;
}
}
return max;
}
// swap方法交换index1和index2之间的数组元素
private static void swap（Segment [] segments，int index1，int index2）{
int temp1;
int temp2;
temp1 = segments [index1] .number;
temp2 = segments [index1] .type;
段[index1] .number = segments [index2] .number;
段[index1] .type = segments [index2] .type;
段[index2] .number = temp1;
段[index2] .type = temp2;
}
selectSort是排序方法（因为Arrays.sort不会使用段 ）
private static void selectSort（Segment [] segments）{
int MaxPos; （int i = segments.length-1; i> 0; i - ）{
MaxPos = maxI（segments，i + 1）;
交换（段，MaxPos，i）;
}
}
原始输入是2个范围和3个交点：
范围1：0 5
范围2：6 10
交点：1 6 11
所以排序后，结果如下：
< （0,1），（1,0），（5,1），（6,0），（6，-1），（10,1），（ 11,0）
我试图修改maxI方法，所以6，-1来了6,0（-1 <0）使用第二个if语句：
if（segments [i] .number =段[max] .number&& segments [i] .type>片段[max] .type）
但是它混淆了输出。由于输入是随机的，代码必须准备好排序许多数字相等的测试用例。
只需创建一个比较器比较号码然后键入，然后您可以使用 Arrays.sort（）。如果你有Java 8，你可以这样做：
Arrays.sort（points，Comparator.comparingInt（（Segment s ） - > s.number）.thenComparingInt（（Segment s） - > s.type））;
如果您使用Java 7，可以这样做：
Arrays.sort（points，new Comparator< Segment>（）{
@Override
public int compare（Segment s1，Segment s2） {
int result = Integer.compare（s1.number，s2.number）;
if（result == 0）{
result = Integer.compare（s1.type，s2.type ）;
}
返回结果;
}
}）;
或者，您可以拥有细分实现可比较的界面和 Arrays.sort（points）将开箱即用：
private static class段实现Comparable< Segment> {
int number，type;
段（int number，int type）{
this.number = number;
this.type = type;
}
@Override
public int compareTo（Segment s）{
int result = Integer.compare（this.number，s.number）;
if（result == 0）{
result = Integer.compare（this.type，s.type）;
}
返回结果;
}
}
I have a class Segment and an array of segments like this:
private static class Segment {
int number, type;
Segment(int number, int type) {
this.number = number;
this.type = type;
}
}
Segment[] points = new Segment[n];
points={(0,-1),(1,0),(5,1),(6,0),(6,-1),(10,1),(11,0)}
The element of the left is a list of points, and the list of the right is the type of point: -1 opens a segment, 1 closes a segment and 0 intersects the segment. As you can see, this array is already sorted according to number, using this code (its an adapted selectionSort):
maxI finds the index of the biggest "number" element
private static int maxI(Segment[] segments, int size){
int max=0;
for (int i=0; i< size;i++){
if(segments[i].number > segments[max].number ){
max=i;
}
}
return max;
}
// swap method swaps elements of the array between index1 and index2
private static void swap(Segment[] segments, int index1, int index2){
int temp1;
int temp2;
temp1 = segments[index1].number;
temp2 = segments[index1].type;
segments[index1].number=segments[index2].number;
segments[index1].type=segments[index2].type;
segments[index2].number=temp1;
segments[index2].type=temp2;
}
selectSort is the sorting method (since Arrays.sort wont work with "segments")
private static void selectSort(Segment[] segments) {
int MaxPos;
for (int i=segments.length-1;i>0;i--){
MaxPos = maxI(segments, i+1);
swap (segments, MaxPos, i);
}
}
The original input was 2 ranges and 3 intersection points:
Range 1: 0 5
Range 2: 6 10
Intersection points: 1 6 11
So after sorting, the result as above is:
(0,-1),(1,0),(5,1),(6,0),(6,-1),(10,1),(11,0)
I've tried to modify the maxI method, so 6,-1 comes before 6,0 (-1 < 0) using a second if statement:
if (segments[i].number = segments[max].number && segments[i].type > segments[max].type)
But it messes the output.Since the input is random, the code must be prepared to sort testcases where many numbers are equal.
The closest question I've seen with this subject is one made in C++, I'm just learning Java so I'm struggling enough to try to understand C++. I feel the answer is close, but not sure what am I missing.Maybe I'm using the wrong data structure. After this I just traverse the array, adding the sum of the types, so if a number passes 3 opening of ranges (x,-1), it's -3,in absolute= 3 so it's intersecting 3 ranges, which is the answer I'll need.
Just create a Comparator that compares number then type, then you can use Arrays.sort(). If you have Java 8, you can do it like this:
Arrays.sort(points, Comparator.comparingInt((Segment s) -> s.number).thenComparingInt((Segment s) -> s.type));
If you're using Java 7, you can do this:
Arrays.sort(points, new Comparator<Segment>() {
@Override
public int compare(Segment s1, Segment s2) {
int result = Integer.compare(s1.number, s2.number);
if (result == 0) {
result = Integer.compare(s1.type, s2.type);
}
return result;
}
});
Alternatively, you can have Segment implement the Comparable interface, and Arrays.sort(points) will work out of the box:
private static class Segment implements Comparable<Segment> {
int number, type;
Segment(int number, int type) {
this.number = number;
this.type = type;
}
@Override
public int compareTo(Segment s) {
int result = Integer.compare(this.number, s.number);
if (result == 0) {
result = Integer.compare(this.type, s.type);
}
return result;
}
}
这篇关于如何按照升序排序一个数组（int left，int right），但是如果left（i）= left（i + 1）将其排序到右（i）和右（i + 1）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
