1、java数组定义
1、与其他高级语言不同，Java在数组声明时并不为数组分配存储空间,因此，在声明的[]中不能指出数组的长度
2、为数组分配空间的两种方法：数组初始化和使用new运算符
3、未分配存储空间时，数组变量中只是一个值为null的空引用，要访问数组元素，必须需要经过初始化、分配存储空间创建数组后才能访问数组的元素
一维数组定义：
int[] arr; //注意int[5] arr；错误 int arr[]; int[] arr = {1, 2, 3, 4, 5}; int[] arr = new int[5];
二维数组定义：
二维数组即是特殊的一维数组，每个元素是一个一维数组
int[] arr[]; //此种方式最好理解
int arr[][];
int[][] arr;
int arr[][] = {{1,2},{3,4},{5,6,7}};
int arr[][] = new int[3][3]
2. 二进制数种1的位数
注意：
1. 方式一通过右移计算，如果是负数右移时高位会补充0，此时可能会进入死循环
如4（100）返回1， 9（1001）返回2
public class BitCount { //方式一：移位加计数器 注意java中没有无符号整形 public static int bitCount(int n){ int count = 0; while(n > 0){ if((n & 1) == 1){ count++; } n >>= 1; } return count; }
public static int bitCount1(int n){ int count = 0; unsigned int flag = 1; while(flag){ if(n&flag){ count++; } flag = flag << 1; } return count; }
//方式三：使用n = n & (n-1) public static int bitCount2(int n){ int count = 0; while(n > 0){ n &= n-1; //消除最右边的1,和第一种方式等价，只是这个的执行次数由数字中的1决定 count++; } return count; }
public static void main(String[] args) {
System.out.println("3: "+ bitCount(3));
System.out.println("8: "+ bitCount(8));
System.out.println("11: "+ bitCount(11));
System.out.println("6: "+ bitCount2(6));
System.out.println("7: "+ bitCount2(7));
System.out.println("13: "+ bitCount2(13));
}
}
输出：
3: 2 8: 1 11: 3 6: 2 7: 3 13: 3
http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html 中提供了很多其他很巧妙的方法
3.无序数组中最小的10个数
需要考虑数组是否可以修改
1）如果数组可以修改, 时间复杂度O(n)
可以参考快速排序的思路，基于数组的第k个数字来排序，使得比k小的所有数字排在数组的左边，比k大的数字排在数组的右边；另外这种方式找出的前k个数不一定是有序的
借用快速排序中partition函数
public static int partition(int[] data, int start, int end){ if(data == null || start < 0 || end >= data.length){ throw new InvalidParameterException(); } Random rand = new Random(); int index = rand.nextInt(end-start+1)+start; swap(data, index, end); int borderPos = start-1; //记录小于部分和大于部分的分界点,指向最后一个小于的值 for(index = start; index < end; ++index){ if(data[index] < data[end]){ borderPos++; if(borderPos != index){ swap(data, borderPos, index); } } } borderPos++; swap(data, borderPos, end); return borderPos; } public static void swap(int[] data, int pos1, int pos2){ int tmp = data[pos1]; data[pos1] = data[pos2]; data[pos2] = tmp; }
查找最小的前k个数
public static int[] getSmallestNum(int[] numbers, int k){ if(numbers == null || k <= 0 || k > numbers.length){ throw new InvalidParameterException(); } int start = 0, end = numbers.length -1, index = partition(numbers, start, end); while(index != k-1){ if(index > k-1){ end = index - 1; index = partition(numbers, start, end); }else{ start = index + 1; index = partition(numbers, start, end); } } int[] result = new int[k]; for(int i = 0; i < k; i++){ result[i] = numbers[i]; } return result; }
测试：
public static void main(String[] args) { int[] arr = new int[20]; for(int i=0; i<20; i++){ arr[i] = (int) (Math.random()*100); } for(int i=0,len=arr.length; i<len; i++){ System.out.print(arr[i]+" "); } int[] result = getSmallestNum(arr,5); System.out.println(""); for(int i=0,len=result.length; i<len; i++){ System.out.print(result[i]+" "); }
输出：
91 69 75 29 69 55 80 44 63 19 36 53 62 45 97 52 8 93 34 38 29 19 8 34 36
2) 使用大根堆
使用大根堆存储最小的k个数，将前k个数读入堆中，剩下的数据和堆中的最大值比较，小于最大值即替换最大值，如果比最大值大，丢弃该值，，大根堆的插入和删除时间复杂度为O(logk),因而整体的时间复杂度为O(nlogk)
此种方式不用更改数组，并且适合处理海量数据
public static int[] getSmallestNums1(int[] numbers, int k){ //参数检查 if(numbers == null || k <= 0){ throw new InvalidParameterException(); } //存储大根堆，初始值为numbers的前k个数 int[] heap = new int[k]; for(int i = 0; i < k; i++){ heap[i] = numbers[i]; } int rootIndex = k/2 -1; while(rootIndex >= 0){ reheap(heap, rootIndex, k-1); rootIndex--; } for(int i = k, len = numbers.length; i < len; i++){ //如果数值比最大值小，替换最大值 if(numbers[i] < heap[0]){ heap[0] = numbers[i]; reheap(heap, 0, k-1); } } return heap; } //重建大根堆 public static void reheap(int[] heap, int rootIndex, int end){ int node = heap[rootIndex]; int leftIndex = rootIndex*2 +1; boolean done = false; while(!done && leftIndex <= end){ int index = leftIndex; if(leftIndex+1 <= end){ int rightIndex = leftIndex + 1; if(heap[rightIndex] > heap[leftIndex]){ index = rightIndex; } } if(node < heap[index]){ heap[rootIndex] = heap[index]; rootIndex = index; leftIndex = rootIndex*2 + 1; }else{ done = true; } } heap[rootIndex] = node; }
测试：
public static void main(String[] args) { int[] arr = new int[20]; for(int i=0; i<20; i++){ arr[i] = (int) (Math.random()*100); } for(int i=0,len=arr.length; i<len; i++){ System.out.print(arr[i]+" "); } int[] result = getSmallestNums1(arr,5); System.out.println(""); for(int i=0,len=result.length; i<len; i++){ System.out.print(result[i]+" "); } }
输出：
91 13 44 34 3 57 62 89 57 62 45 1 40 71 76 18 1 28 32 55 18 13 1 1 3