删除数组中重复元素
删除元素可以直接用Set集合，他会自动将重复的元素给去掉（下方注释的代码）
在一个给定的整型数组中，如何快速找到缺失的数字
假设一个长度为10的数组范围为1-9，快速定位到缺失的元素;定义一个map集合，以1-9为键，值为0，然后拿到上面数组的去遍历，相同则将值设为1，让后再去遍历map，值为0的键就是缺失的那个元素
public static void main(String[] args) {
//删除数组中重复的参数
/* Object[] arr = {1,1,1,2,3,3,4,5,"夏","夏","冬","春",};
Set set = new HashSet();
//遍历数组并存入集合,如果元素已存在则不会重复存入
for (int i = 0; i < arr.length; i++) {
set.add(arr[i]);
}
//返回Set集合的数组形式
System.out.println(set.toArray());
*/
//在一个给定的整型数组中，如何快速找到缺失的数字
List<Integer> ints = new ArrayList<>();
ints.add(1);
ints.add(2);
ints.add(3);
ints.add(4);
ints.add(5);
ints.add(6);
ints.add(7);
ints.add(8);
ints.add(8);
ints.add(9);
HashMap<Object, Object> map = new HashMap<Object,Object>();
map.put(1, 0);
map.put(2, 0);
map.put(3, 0);
map.put(4, 0);
map.put(5, 0);
map.put(6, 0);
map.put(7, 0);
map.put(8, 0);
map.put(9, 0);
map.put(10, 0);
for(Integer i : ints) {
if(null!=map.get(i)) {
map.put(i,1);
}
}
for(Entry<Object, Object> entry : map.entrySet()) {
if(entry.getValue().equals(0)) {
System.out.println(entry.getKey());
}
}
}
快速排序
static void quickSort(int[] arr,int left,int right) //快速排序算法
{
int f,t;
int rtemp,ltemp;
ltemp = left;
rtemp = right;
f=arr[(left+right)/2]; //分界值
while(ltemp<rtemp)
{
while(arr[ltemp]<f){
++ltemp;
}
while(arr[rtemp]>f){
--rtemp;
}
if(ltemp<=rtemp){
t=arr[ltemp];
arr[ltemp]=arr[rtemp];
arr[rtemp]=t;
--rtemp;
++ltemp;
}
}
if(ltemp==rtemp){
ltemp++;
}
if(left<rtemp){
quickSort(arr,left,ltemp-1); //递归调用
}
if(ltemp<right){
quickSort(arr,rtemp+1,right); //递归调用
}
}
也可以直接使用
Arrays.sort(int[] arr)
注意：
Arrays.sort（） 无法直接对int【】数组进行降序排列，只能进行升序排列。
在使用排序时如果要求效率，最好使用int类型，而不是使用Integer类型，这样可以省去自动包装和拆包时所需要耗费的大量时间。
数组反转
直接使用数组实现反转
/**
* 没有考虑效率的反转
*
* @param array
* @return
*/
private static int[] reverse1(int[] array) {
int[] newArray = new int[array.length];
for (int i = 0; i < array.length; i++) {
newArray[i] = array[array.length - 1 - i];
}
return newArray;
}
/**
* 考虑时间复杂度和空间复杂度的反转
*
* @param array
* @return
*/
private static int[] reverse2(int[] array) {
int temp;
for (int i = 0; i < array.length / 2; i++) {
temp = array[i];//将当前值赋给变量
array[i] = array[array.length - 1 - i];//将后面的数据替换前面的数据
array[array.length - 1 - i] = temp;//拿到前面的值赋后面
}
return array;
}
通过工具类
Collections.reverse(int[] array);
在指定数组中查找重复数字
public static int findDuplicate(int[] nums) {
if(nums == null||nums.length == 0) {
return -1;
}
// 修改数组的方法 O(n)
for (int i = 0; i < nums.length; i++) {
while (nums[i] - 1 != i) {
int b = nums[i] - 1; // i所在的index
int e = nums[b]; // i所在的index的值
if (e == nums[i]) {
return e;
} else { // 不一样 swap
int tmp = nums[b];
nums[b] = nums[i];
nums[i] = tmp;
}
}
}
return 0;
}
求数组最大值
一般求数组最大值是通过遍历整个数据来获得最大值，这样遍历速度是O(n)
public static void getMax(int[] arr) {
int max = arr[0];
for(int i=1;i<arr.length;i++) {
if(arr[i]>max) {
max = arr[i];
}
}
System.out.println("该数组中最大的值为"+max);
}
现在假设数组的元素从前到后先升序后降序，如果采用二分法的话可以相比较遍历全部而言他的速度是O（logn）。
public static void main(String[] args) {
int[] arr = {3,4,5,6,7,8,9,10,11,12,13,10,9,8,7,6,4,3,2,1};
int len = arr.length;
// 当只有一个数时，直接返回
if (len == 1) {
System.out.println(arr[0]);
}
// 当数组只有下降部分时，直接返回
if (arr[0] > arr[1]) {
System.out.println(arr[0]);
}
// 当数组只有上升部分时，直接返回
if (arr[len - 1] > arr[len - 2]) {
System.out.println(arr[len - 1]);
}
// 接下来处理既有上升部分又有下降部分的数组（这样的数组至少有3个元素）
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = (int) Math.floor((left + right) / 2);
// 判断arr[mid]是否为最大值
if (mid != 0 && arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
System.out.println(arr[mid]);
}
// 当arr[mid]不是最大值时，判断arr[mid]处于数组上升部分还是下降部分
if (mid == 0 || arr[mid] > arr[mid - 1]) {
// 处于上升部分
left = mid + 1;
System.out.println("left" + arr[left]);
} else if (arr[mid] < arr[mid - 1]) {
// 处于下降部分
right = mid - 1;
System.out.println("right" + arr[right]);
}
}
System.out.println(arr[right]);
}
