大侠进来看看这个小程序怎么实现？
有一递增数列，当插入一个数后使得该数列仍然保持递增，那位大侠给出段关键代码！！ 先谢了。
[解决办法]
import java.util.*;
public class LinkedListTest
{
private LinkedList <String> list = new LinkedList <String> ();
public LinkedListTest()
{}
public void insert(int num)
{
int i=0;
for( i=0;i <list.size();i++)
{
String temp = (String)list.get(i);
if(Integer.parseInt(temp)> =num)
{
break;
}
}
list.add(i,String.valueOf(num));
}
public void play()
{
for(int i=0;i <list.size();i++)
{
System.out.print( "--- "+list.get(i));
}
System.out.println();
}
public static void main(String args[])
{
LinkedListTest t = new LinkedListTest();
t.insert(1);
t.insert(3);
t.insert(4);
t.insert(5);
t.play();
t.insert(2);
t.play();
}
}
[解决办法]
既然是排好的序列,用binarySearch就行了.
import java.util.*;
public class T {
public static void main(String[] args) {
ArrayList al = new ArrayList();
al.add(1);
al.add(4);
al.add(14);
al.add(28);
int i = 13;
int index = Collections.binarySearch(al, i);
if(index > = 0)
al.add(index, i);
else
al.add(-index-1, i);
System.out.println(al);
}
}
[解决办法]
楼住如果仅仅是为了保证元素的有序排列，给你个最简单的，用TreeSet就可以了。缺点是不允许插入重复的值，看楼主用途了。
TreeSet <Integer> set = new TreeSet <Integer> ();
set.add(1);
set.add(3);
set.add(5);
System.out.println(set);
set.add(2);
System.out.println(set);
set.add(4);
System.out.println(set);
[解决办法]
基于数组的简单实现,楼主随意看看.
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws Exception {
int[] arr = new int[]{1,3,5,6,8,10};
System.out.println(Arrays.toString(arr));
arr = insert(arr, 2);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 4);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 7);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 9);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 7);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 4);
System.out.println(Arrays.toString(arr));
}
private static int[] insert(int[] arr, int value){
int[] newarr = new int[arr.length+1];
int pos = getIndex(arr,value,0,arr.length-1);
newarr[pos] = value;
System.arraycopy(arr, 0, newarr, 0, pos);
System.arraycopy(arr, pos, newarr, pos+1, arr.length-pos);
return newarr;
}
private static int getIndex(int[] arr, int i, int start, int end){
int index = (end-start)/2+start;
int mid = arr[index];
if(end - start > 1){
if(mid > i){
return getIndex(arr,i,start,index);
}
else if(mid < i){
return getIndex(arr,i,index,end);
}
}
return index+1;
}
}
[解决办法]
用binarySearch实现的
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws Exception {
int[] arr = new int[]{3,1,5,6,8,10};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 2);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 4);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 7);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 9);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 7);
System.out.println(Arrays.toString(arr));
arr = insert(arr, 4);
System.out.println(Arrays.toString(arr));
}
private static int[] insert(int[] arr, int value){
int[] newarr = new int[arr.length+1];
int pos = newarr.length-1;
int index = Arrays.binarySearch(arr, value);
if(index > =0 ){
pos = index;
System.arraycopy(arr, 0, newarr, 0, pos);
System.arraycopy(arr, pos, newarr, pos+1, arr.length-pos);
}
else{
pos = -index-1;
System.arraycopy(arr, 0, newarr, 0, pos);
System.arraycopy(arr, pos, newarr, pos+1, arr.length-pos);
}
newarr[pos] = value;
return newarr;
}
}
