一个编程题的几种算法比较
class HighArray
{
private long[] a; // ref to array a
private int nElems; // number of data items
//-----------------------
public HighArray(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
//-----------------------
public boolean find(long searchKey)
{ // find specified value
int j;
for(j=0; j<nElems; j++) // for each element,
if(a[j] == searchKey) // found item?
break; // exit loop before end
if(j == nElems) // gone to end?
return false; // yes, can't find it
else
return true; // no, found it
} // end find()
//-----------------------
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
//-----------------------
public boolean delete(long value)
{
int j;
for(j=0; j<nElems; j++) // look for it
if( value == a[j] )
break;
if(j==nElems) // can't find it
return false;
else // found it
{
for(int k=j; k<nElems; k++) // move higher ones down
a[k] = a[k+1];
nElems--; // decrement size
return true;
}
} // end delete()
//-----------------------
public void noDup() {
for(int i=0;i<nElems;i++) {
for(int j =i+1;j<nElems;j++) {
if(a[i]==a[j]) {
a[j] = -1;
}
}
}
for(int i=nElems-1; i>=0; i--) {
if(a[i] == -1)
delete(-1);
}
}
//-----------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
//-----------------------
} // end class HighArray
////////////////////////////////////////////////////////////////
class HighArrayApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
HighArray arr; // reference to array
arr = new HighArray(maxSize); // create the array
arr.insert(77); // insert 10 items
arr.insert(77);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // display items
int searchKey = 35; // search for item
if( arr.find(searchKey) )
System.out.println("Found " + searchKey);
else
System.out.println("Can't find " + searchKey);
arr.delete(00); // delete 3 items
arr.delete(55);
arr.delete(99);
arr.insert(55);
arr.insert(44);
arr.insert(44);
arr.insert(55);
arr.display();
arr.noDup();
arr.display(); // display items again
} // end main()
} // end class HighArrayApp
------------------------------------------
作业要求:向highArray.java程序(清单2.3)的HighArray类中加入一个noDup()的方法,使之可以将数组中的所有重复数据项删除.即如果数组中有三个数据项的关键字为17, noDup()方法将会删除其中的两个.不必考试保持数据项的顺序.一种方法是先用每一个数据项比较,并用null（或是一个不会用在真正的关键字中的特殊值）将重复的数据项覆盖掉。然后将所有的null删除，当然还要缩小数组的大小。
下面的noDup()是我的方法：
------------------------------------------------------
public void noDup() {
for(int i=0;i<nElems;i++) {
for(int j =i+1;j<nElems;j++) {
if(a[i]==a[j]) {
a[j] = -1;
}
}
}
for(int i=nElems-1; i>=0; i--) {
if(a[i] == -1)
delete(-1);
}
}
---------------------------------
还有一种是方法是这样的，麻烦大家比较下这2种方法有区别嘛，哪个比较好一些呢？
public void noDup(){
//标记部分
int nCount = 0; //标记计数器。
for(int i=0; i<nElems; i++)
for(int j=0; j<i; j++)
if(a[j] == a[i])
{
if(a[i] != -1) //排除特殊标记
{
a[i] = -1; //特殊标记，假设用户不会输入负值。
nCount++;
}
}
//调整部分
long[] b = new long[nElems - nCount];
int nLength = 0;
int nVariable = 0;//变数，根据-1值变化调整下标。
for(int i=0; i<nElems; i++){
if(a[i] != -1){
//文字常量，通过它计算实际数组下标，数组下标从０开始。
b[nElems - nCount - 1 + nVariable - i] = a[i];
nLength++;
}
else
nVariable++;
}
//赋值部份
nElems = nLength;
a = b;
}
[解决办法]
你的排重的方法时间复杂度是O（n^2)，最后去重的时候，第一种方法要频繁的移动数组元素，从这个角度来说，第二种方法要好些。
[解决办法]
有意思！
顶起！
[解决办法]
其实你可以把数组中的数全部存到set里面去,因为set里面的元素是不能重复的,然后把它取出来放到数组中去.这样就不用判断了
public static void main(String[] args) { Set<Long> set=new HashSet<Long>(); long[] a=new long[]{1,2,1,3,5,4,2}; for(int i=0;i<a.length;i++){ set.add(a[i]); } Iterator<Long> it=set.iterator(); for(int i=0;i<set.size();i++){ a[i]=it.next(); System.out.println(a[i]+" "); } }