一种排序--引发：java两个引用指向同一个对象

地址：http://acm.nyist.net/JudgeOnline/problem.php?pid=8

一种排序

时间限制：3000 ms | 内存限制：65535 KB难度：3

描述

现在有很多长方形，每一个长方形都有一个编号，这个编号可以重复；还知道这个长方形的宽和长，编号、长、宽都是整数；现在要求按照一下方式排序（默认排序规则都是从小到大）；

1.按照编号从小到大排序

2.对于编号相等的长方形，按照长方形的长排序；

3.如果编号和长都相同，按照长方形的宽排序；

4.如果编号、长、宽都相同，就只保留一个长方形用于排序,删除多余的长方形；最后排好序按照指定格式显示所有的长方形；

输入

第一行有一个整数 0<n<10000,表示接下来有n组测试数据；
每一组第一行有一个整数 0<m<1000，表示有m个长方形；
接下来的m行，每一行有三个数，第一个数表示长方形的编号，

第二个和第三个数值大的表示长，数值小的表示宽，相等
说明这是一个正方形（数据约定长宽与编号都小于10000）；

输出

顺序输出每组数据的所有符合条件的长方形的编号长宽

样例输入

样例输出

由题目：要注意一点：第二个和第三个数值大的表示长，数值小的表示宽，相等。

需要对长和宽进行处理。

思路：

其实也很简单，就是一种升序的排列，还要涉及到权重，权重（编号>长>宽），只有相等的时候，才需要比较下一个等级。并且，一个尤其重要的是：涉及到交换和移动的时候一定要整体进行。而且测试用例有点坑嗲，如果你交换或移动没有整体性的话，得出的结果和测试用例是一样的。这就导致为什么很多人士wrong answer 的。。---我就是其中一个。

第一种方法：（同样是用插入排序，把他写熟了，性能是怎么都好过冒泡排序的）

//暴力的插入排序，思想很简单，根据权重顺序进行排列，相等的时候，继续比较下一个（权重：编号，长，宽）不过不知道为何wrong answer，感觉思路是没有错的--原来是要整体性交换
public void insertSortOne(Scanner sc){
int n=sc.nextInt();
while(n-->0){
int m=sc.nextInt();
int[] numArr=new int[m];
int[] longArr=new int[m];
int[] widthArr=new int[m];
int tmpN,tmpL,tmpW,tmp;
for(int i=0;i<m;i++){
tmpN=sc.nextInt();//得到编号
tmpL=sc.nextInt();
tmpW=sc.nextInt();
if(tmpW>tmpL){//得到长和宽
tmp=tmpW;
tmpW=tmpL;
tmpL=tmp;
}
//插入排序--先实现，后面再优化--交换的时候，要当成一个整体进行交换，不是就会错，而且给出的测试案例特殊，不交换测试案例也是对的。但是肯定是wrong answer
int j=i;
while(j>0&&tmpN<numArr[j-1]){//若相同跳出，插在后一个
numArr[j]=numArr[j-1];
longArr[j]=longArr[j-1];
widthArr[j]=widthArr[j-1];
j--;
}
numArr[j]=tmpN;
if(j!=0&&numArr[j]==numArr[j-1]){  //不在数组第一位的时候,且当前和前一个相同时，就比较长
//对长进行插入排序
int l=j;
while(l>0&&tmpL<longArr[l-1]){
numArr[l]=numArr[l-1];
longArr[l]=longArr[l-1];
widthArr[l]=widthArr[l-1];
l--;
}
longArr[l]=tmpL;
if(l!=0&&longArr[l]==longArr[l-1]){
//对宽进行排列
int w=l;
while(w>0&&tmpW<widthArr[w-1]){
numArr[w]=numArr[w-1];
longArr[w]=longArr[w-1];
widthArr[w]=widthArr[w-1];
w--;
}
widthArr[w]=tmpW;
if(w!=0&&widthArr[w]==widthArr[w-1]){
//说明三个都相等，把他去掉
i--;//重新填充i，即可
m--;//相应把for循环的长度给缩小
}
}
else{
widthArr[l]=tmpW;
}
}
else{
longArr[j]=tmpL;
widthArr[j]=tmpW;
}

}
//进行输出结果
for(int i=0;i<m;i++)
System.out.println(numArr[i]+" "+longArr[i]+" "+widthArr[i]);
}
}

第二中方法：

就是声明一个内部类，将编号，长，宽放进去。通过get,set进行修改，也是一种封装的思想（但是一个开始不是这样的，贪图方便）。尤其是插入排序，一定为涉及到数组对象的移动的。

使用前必须实例化一个对象先：rectangle[i]=new Rectangle();

直接把它写成：rectangle[j]=rectangle[j-1];对象数组存的是一个对象引用，前面这样先，相当于拷贝，即：两个引用指向了同一个对象，无论通过修改那个引用，必定会修改到同一个对象，具体查看：浅拷贝和深拷贝。留个网址（不一定是最好的）：http://kuangbaoxu.iteye.com/blog/193222

所以必须做出修改，通过get，set进行赋值，移动或者用集合，暂时没想到

rectangle[j].setNum(rectangle[j-1].getNum());
rectangle[j].setLeng(rectangle[j-1].getLeng());
rectangle[j].setWidth(rectangle[j-1].getWidth());

附上方法二：

public void insertSortTwo(Scanner sc){

int n=sc.nextInt();
while(n-->0){
int m=sc.nextInt();

Rectangle[] rectangle=new Rectangle[m];
int tmpN,tmpL,tmpW,tmp;
for(int i=0;i<m;i++){
rectangle[i]=new Rectangle();//先实例化出一个对象
tmpN=sc.nextInt();
tmpL=sc.nextInt();
tmpW=sc.nextInt();
if(tmpL<tmpW){//先得出符合规则的长和宽，编号
tmp=tmpL;
tmpL=tmpW;
tmpW=tmp;
}
int j=i;
while(j>0&&tmpN<rectangle[j-1].num){
//rectangle[j]=rectangle[j-1];//涉及到深拷贝和浅拷贝问题,（对象数组的引用到了同一个对象。即：内存中是两个引用指向了同一个对象，
//java机制是不会分配完全两个相同的对象的不同空间的，除非有不同（hascode()不同皆可））
rectangle[j].setNum(rectangle[j-1].getNum());
rectangle[j].setLeng(rectangle[j-1].getLeng());
rectangle[j].setWidth(rectangle[j-1].getWidth());
j--;
}
rectangle[j].num=tmpN;
if(j!=0&&rectangle[j].getNum()==rectangle[j-1].getNum()){
//编号相同，进行长排序
int l=j;
while(l>0&&tmpL<rectangle[l-1].leng){
//rectangle[l]=rectangle[l-1];
rectangle[l].setNum(rectangle[l-1].getNum());
rectangle[l].setLeng(rectangle[l-1].getLeng());
rectangle[l].setWidth(rectangle[l-1].getWidth());
l--;
}
rectangle[l].leng=tmpL;
if(l!=0&&rectangle[l].getLeng()==rectangle[l-1].getLeng()){
//进行宽的排序
int w=l;
while(w>0&&tmpW<rectangle[w-1].width){
//rectangle[w]=rectangle[w-1];
rectangle[w].setNum(rectangle[w-1].getNum());
rectangle[w].setLeng(rectangle[w-1].getLeng());
rectangle[w].setWidth(rectangle[w-1].getWidth());
w--;
}
rectangle[w].width=tmpW;
if(w!=0&&rectangle[w].getWidth()==rectangle[w-1].getWidth()){
i--;
m--;
}
}
else{
rectangle[l].setWidth(tmpW);
}

}
else{//不同的话，将相应赋值
rectangle[j].setLeng(tmpL);
rectangle[j].setWidth(tmpW);
}
}
for(int i=0;i<m;i++)
System.out.println(rectangle[i].getNum()+" "+rectangle[i].getLeng()+" "+rectangle[i].getWidth());
}
}
class Rectangle{
private int num,leng,width;

public int getNum() {
return num;
}

public void setNum(int num) {
this.num = num;
}

public int getLeng() {
return leng;
}

public void setLeng(int leng) {
this.leng = leng;
}

public int getWidth() {
return width;
}

public void setWidth(int width) {
this.width = width;
}

}

这题耗时挺长的，主要是纠结怎么错了，并通过这道题发现自己的不足，也是查漏补缺的机会，现在耗时长，以后就会耗时短了。

以上都是wrong answer。还以为对了。不明觉厉。

最后附上一个通过的--用的冒泡排序，难道这道题不能用插入排序？？？

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
public static Scanner scanner = new Scanner(new BufferedInputStream(
System.in));

public static void main(String[] args) {
int count = scanner.nextInt();
for (int i = 0; i < count; i++) {
int longer = scanner.nextInt();
int[] num = new int[longer];
int[] length = new int[longer];
int[] wide = new int[longer];
for (int j = 0; j < longer; j++) {
num[j] = scanner.nextInt();
length[j] = scanner.nextInt();
wide[j] = scanner.nextInt();
if (length[j] < wide[j]) {
int temp = length[j];
length[j] = wide[j];
wide[j] = temp;
}
}
for (int j = 0; j < longer - 1; j++) {
for (int k = j + 1; k < longer; k++) {
if (num[j] < num[k]) {
int temp = num[j];
num[j] = num[k];
num[k] = temp;
temp = length[j];
length[j] = length[k];
length[k] = temp;
temp = wide[j];
wide[j] = wide[k];
wide[k] = temp;
} else if (num[j] == num[k] && length[j] < length[k]) {
int temp = num[j];
num[j] = num[k];
num[k] = temp;
temp = length[j];
length[j] = length[k];
length[k] = temp;
temp = wide[j];
wide[j] = wide[k];
wide[k] = temp;
} else if (num[j] == num[k] && length[j] == length[k]
&& wide[j] < wide[k]) {
int temp = num[j];
num[j] = num[k];
num[k] = temp;
temp = length[j];
length[j] = length[k];
length[k] = temp;
temp = wide[j];
wide[j] = wide[k];
wide[k] = temp;
} else if (num[j] == num[k] && length[j] == length[k]
&& wide[j] == wide[k]) {
num[j] = Integer.MAX_VALUE;
}
}
}
for (int j = longer - 1; j >= 0; j--) {
if (num[j] != Integer.MAX_VALUE) {
System.out
.println(num[j] + " " + length[j] + " " + wide[j]);
} else {
continue;
}
}
}
}
}

秒客网

一种排序--引发：java两个引用指向同一个对象

一种排序

相关文章