@TOC
一.奇数位于偶数之前
调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
如数组：[1,2,3,4,5,6]
调整后可能是：[1, 5, 3, 4, 2, 6]
1.方法1：
public static void order(int[] arr) {
int[] arr1 = Arrays.copyOf(arr,arr.length);
int j = 0;
for (int i = 0; i < arr.length; i++) {
if(arr1[i]%2 != 0) {
arr[j++]=arr1[i];
}
}
for (int i = 0; i < arr.length; i++) {
if(arr1[i]%2 == 0) {
arr[j++]=arr1[i];
}
}
}
public static void main(String[] args) {
//奇数位于偶数之前
int[] arr = {1,2,3,4,5,6};
order(arr);
for (int x: arr) {
System.out.print(x+" ");
}
}方法2：
public static void order(int[] arr) {
int i = 0;
int j = arr.length - 1;
while (i < j) {
while (i < j && arr[i] % 2 != 0) {
i++;
}
while (i < j && arr[j] % 2 == 0) {
j--;
}
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
public static void main(String[] args) {
int[] arr = {1,3,2,4,7,6};
order(arr);
for (int x: arr) {
System.out.println(x+" ");
}
}二.改变原有数组元素的值
实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素 乘以 2 , 并设置到对应的数组元素上. 例如 原数组为 {1, 2, 3}, 修改之后为 {2, 4, 6}
public static void tran(int[] arr) {
for (int i = 0; i < arr.length; i++) {
arr[i]*=2;
}
}
public static void main(String[] args) {
//改变原有数组元素的值
int[] arr = {1,2,3};
tran(arr);
for (int x: arr) {
System.out.print(x+" ");
}
}三.求数组的平均值
实现一个方法 avg, 以数组为参数, 求数组中所有元素的平均值(注意方法的返回值类型).
public static double avg(int[] arr) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum*1.0/arr.length;
}
public static void main(String[] args) {
//求数组平均值
int[] arr = {1,2,3,4,5,6,7};
double ret = avg(arr);
System.out.println(ret);
}四.二分查找
给定一个有序整型数组, 实现二分查找
public static int binarySearch(int[] arr,int k) {
int left = 0;
int right = arr.length-1;
while(left <= right) {
int mid = (left + right)>>>1;
//int mid = left + (right - left)/2
// int mid = (left + (right - left))>>>1;
if(arr[mid] > k) {
right = mid-1;
}else if(arr[mid] < k) {
left = mid+1;
}else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
//实现二分查找
int[] arr = {1,2,3,4,5,6,7,8,9};
int ret = binarySearch(arr,3);
System.out.println(ret);
}五.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
public static int[] sum(int[] arr,int k) {
int[] arr1 = new int[2];
for (int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
if(arr[i]+arr[j]==k) {
arr1[0] = i;
arr1[1] = j;
return arr1;
}
}
}
return null;
}
public static void main(String[] args) {
//两数之和
int[] arr = {2,7,11,15};
int[] arr1 = sum(arr,9);
if(arr1 == null) {
System.out.println("不存在！");
}
System.out.println(Arrays.toString(arr1));
}六.只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
方法1:
public static void main(String[] args) {
//只出现一次的数字
int[] arr = {4,1,2,1,2};
Arrays.sort(arr);;
for (int i = 1; i < arr.length-1; i++) {
if(arr[0]!=arr[1]) {
System.out.println(arr[0]);
break;
}
if(arr[arr.length-1]!=arr[arr.length-2]){
System.out.println(arr[arr.length-1]);
break;
}
if((arr[i]!=arr[i-1])&&(arr[i]!=arr[i+1])) {
System.out.println(arr[i]);
break;
}
}
}方法2:
//异或法
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,4,3,2,1};
int h = 0;
for (int x: arr) {
h ^= x;
}
System.out.println(h);
}七.多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素
方法1:
//投机取巧法
public static void main(String[] args) {
int[] arr = {2,2,1,1,1,2,2};
Arrays.sort(arr);
System.out.println(arr[arr.length/2]);
}方法2:
public static void main(String[] args) {
//多数元素
int[] arr = {2,2,1,1,1,2,2};
for (int i = 0; i < arr.length; i++) {
int count = 1;
for (int j = i+1; j < arr.length; j++) {
if(arr[j]==arr[i])
count++;
}
if(count > (arr.length)/2) {
System.out.println(arr[i]);
break;
}
}
}方法3:
//投票法
public static int fun(int[] arr) {
int ret = arr[0];
int count = 0;
for (int i = 0; i < arr.length; i++) {
if(arr[i] == ret) {
count++;
}else {
count--;
}
if(count == 0) {
ret = arr[i+1];
}
}
return ret;
}
public static void main(String[] args) {
int[] arr = {2,2,1,1,1,2,2};
int ret = fun(arr);
System.out.println(ret);
}八.存在连续三个奇数的数组
给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false示例一
示例二
方法一:
public static boolean oddNumber(int[] arr) {
for (int i = 0; i < arr.length-2; i++) {
if((arr[i]*arr[i+1]*arr[i+2])%2 == 1) {
return true;
}
}
return false;
}
public static void main(String[] args) {
//存在连续三个奇数
int[] arr = {1,2,3,4,3,4,5,7,23,12};
if(oddNumber(arr)) {
System.out.println("存在！");
}else {
System.out.println("不存在！");
}
}方法二:
public static boolean threeOddNumber(int[] arr) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
if(arr[i]%2 != 0) {
count++;
if(count == 3) {
return true;
}
}else {
//必须置零，否则成为判断数组是否有三个奇数
count = 0;
}
}
return false;
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,3,4,5,7,23,12};
if(threeOddNumber(arr)) {
System.out.println("存在！");
}else {
System.out.println("不存在！");
}
}