1.查找数组中指定元素(二分查找)
以升序排列的数组为例，二分查找的操作逻辑是先获取数组中间位置的元素，随后将待查找的元素与该中间位置的元素进行对比：
若两者相等，那么就找到了目标元素，并返回其在数组中的下标；若待查找元素小于中间元素，便以同样的方式在数组的左半部分开展查找；若待查找元素大于中间元素，则在数组的右半部分用类似方法查找。
public static void main(String[] args) {
int[] array = {2,4,1,23,65,34,89,76,32};
Arrays.sort(array);//排序后升序为:1,2,4,23,32,34,65,76,89
//Arrays.sort()方法能将杂乱无章的数组排列成正序
System.out.println(binarySearch(array, 89));
}
public static int binarySearch(int[] array,int key) {
int left = 0;
int right = array.length - 1;
int mid = array.length / 2;
while(left <= right) {
if(key > array[mid]) {
left = mid + 1;
mid = (left + right) / 2;
}else if(key < array[mid]) {
right = mid - 1;
mid = (left + right) / 2;
}else{
return mid;
}
}
return -1;
}
2.数组排序(冒泡排序)
算法思路
假定要进行升序排序，具体步骤如下：
1. 对数组中相邻的元素从前往后依次比较，若前一个元素比后一个元素大，则进行交换，经过一轮比较后，最大的元素会处于数组的末尾位置。
2. 重复上述过程，直至数组中所有元素都排列整齐。
public static void main(String[] args) {
int[] array = {3,5,1,30,10};
bubble(array);
System.out.println(Arrays.toString(array));
}
public static void bubble(int[] array) {
for (int i = 0; i < array.length; i++) {
boolean flg = false;//排序前将flg设为false
for (int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]) {
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
flg = true;//若发生交换，则将flg设为true，表明顺序还未排好
}
}
if(flg == false) {
break;
}
}
}
3.数组逆序
思路：设定两个下标，分别指向数组的第一个元素和最后一个元素，交换这两个位置的元素。然后让前一个下标自增，后一个下标自减，重复此循环操作。
代码示例
public static void main(String[] args) {
int[] array = {1,2,3,4,5};
reverse(array);
System.out.println(Arrays.toString(array));
}
public static void reverse(int[] array) {
int left = 0;
int right = array.length - 1;
while(left < right) {
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
left++;
right--;
}
}
4.奇数位于偶数之前
调整数组顺序使得奇数处于偶数之前，调整后不关注大小顺序。
思路：使用两个下标，一个从数组的0下标开始，另一个从最后一个下标开始。
public static void main(String[] args) {
int[] array = {1,2,3,4,5};
func(array);
System.out.println(Arrays.toString(array));
}
public static void func(int[] array) {
int i = 0;
int j = array.length-1;
while(i < j) {
while(i < j && array[i] % 2 != 0) {
i++;
}
while(i < j && array[j] % 2 != 1) {
j--;
}
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
5.两数之和
给定一个整数数组 nums 和一个整数目标值 target，需在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。假设每种输入仅有一个答案，且数组中同一个元素在答案里不重复出现，返回顺序任意。
示例 1：
输入：nums = [2,7,11,15]，target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9，所以返回 [0, 1]
public static void main(String[] args) {
int[] array = {2,7,11,15};
int[] array1 = func(array,9);
System.out.println(Arrays.toString(array1));
}
public static int[] func(int[] array,int key) {
for (int i = 0; i < array.length-1; i++) {
for (int j = i+1; j <array.length; j++) {
if(array[i] + array[j] == key) {
int[] arr = {i,j};
return arr;
}
}
}
return new int[]{-1,-1};
}
6.找出只出现一次的元素
给定一个非空整数数组，除了某个元素只出现一次外，其余每个元素均出现两次，找出那个只出现一次的元素。
注意：
1. n ^ n = 0；即两个相同的数字异或结果为0
2. 0 ^ n = n；即0和任何数字异或，结果就是该数字
public static void main(String[] args) {
int[] array = {1,3,3,1,4,8,4};
int ret = func(array);
System.out.println(ret);
}
public static int func(int[] array) {
int ret = array[0];
for (int i = 1; i < array.length; i++) {
ret ^= array[i];
}
return ret;
}
7.存在连续三个奇数的数组
给定整数数组 arr，判断数组中是否存在连续三个元素都是奇数的情况，若存在则返回 true，否则返回 false。
示例 1：
输入：arr = [2,6,4,1]
输出：false
解释：不存在连续三个元素都是奇数的情况。
示例 2：
输入：arr = [1,2,34,3,4,5,7,23,12]
输出：true
解释：存在连续三个元素都是奇数的情况，即 [5,7,23]。
public static void main(String[] args) {
int[] arr = {2,6,4,1};
boolean ret = func(arr);
System.out.println(ret);
int[] arr1 = {1,2,34,3,4,5,7,23,12};
boolean ret1 = func(arr1);
System.out.println(ret1);
}
public static boolean func(int[] array) {
int count = 0;
for (int i = 0; i < array.length; i++) {
if(array[i] % 2 != 0) {
count++;
}
if(count == 3) {
return true;
}
}
return false;
}
相关文章
