java 数组算法
2023-03-23 本文已影响0人
Bfmall
1.给定一个 1-100 的整数数组，请找到其中缺少的数字
思路：利用hashmap，首先将100个数字存入map中，value初始为0；然后遍历数组，找到一个数字，把value更新为1，这样遍历完成后，就找到了那个缺少的数字了。
/**
* 如何在一个1到100的整数数组中找到丢失的数字
*/
public void test01(int[] arr) {
//初始化map，将1-100都放到map里面，value初值为0
Map<Integer, Integer> map = new HashMap<>();
for (int i=1;i<=100;i++) {
map.put(i, 0);
}
//遍历数组，找到一个数字，就更新对应的vaule为1
for (int i=0;i<arr.length;i++) {
map.put(arr[i], 1);
}
//遍历map，如果发现value为0，则找到丢失的数字了，返回
Set<Map.Entry<Integer, Integer>> set = map.entrySet();
Iterator iter = set.iterator();
while (iter.hasNext()) {
Map.Entry<Integer, Integer> entry = (Map.Entry<Integer, Integer>) iter.next();
if (entry.getValue() == 0) {
System.out.println("missing value="+entry.getKey());
}
}
}
测试代码：
public void test() {
List<Integer> list=new ArrayList<>();
int[] arr=new int[99];
Random rd=new Random();
//随机生成长度99的数组，不包含重复数字
while(list.size()<99){
int a=rd.nextInt(100)+1;
if(!list.contains(a)){
list.add(a);
}
}
//将list中的值赋给数组
for(int i=0;i<99;i++){
arr[i]=list.get(i);
}
//将数组排序，以便观察检验
Arrays.sort(arr);
test01(arr);
}
2.如何在未排序整数数组中找到最大值和最小值?
思路：创建两个变量 max 和 min 分别记录数组中的最大值和最小值，它们的初始值都是数组中的第一个数字。从第 2 个数字开始遍历数组，每遇到一个比 max 大的数字，就将它存储到 max 变量中；每遇到一个比 min 小的数字，就将它存储到 min 变量中。直到遍历完整个数组，max 记录的就是数组中的最大值，min 记录的就是数组中的最小值。
/**
* 如何在未排序整数数组中找到最大值和最小值?
* //int[] arr = {8,9,3,1,5,6,10};
* @param arr
*/
public void test02(int[] arr) {
int min;
int max;
if (arr != null && arr.length > 0) {
min = arr[0];
max = arr[0];
for (int i=1;i<arr.length;i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
System.out.println("min="+min+", max="+max);
}
}
3.给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。要求：空间复杂度O(1)，时间复杂度为O（n）
思路：
分别从数组两端向中间推进，推出条件为左右相撞。
当左端值为偶数，并且右端值为奇数时交换二值，用到一个临时空间。
当左端值为奇数，向右推进一个单位。
当右端值为偶数，向左推进一个单位。
3.1实现代码：
/**
* 给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。要求：空间复杂度O(1)，时间复
* 杂度为O（n）。
* //int[] arr = {8,9,3,1,5,6,10};
* 输出结果：
* 排序后的数组：[5, 9, 3, 1, 8, 6, 10]
*/
public void test03(int[] arr) {
if (arr != null && arr.length > 0) {
int i = 0;
int j = arr.length - 1;
int temp;
while (i < j) {
if (isEvenNumber(arr[i]) && !isEvenNumber(arr[j])) {
//需要交换位置
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
if (!isEvenNumber(arr[i])) {
//如果arr[i]是奇数，i向右移动
i ++;
}
if (isEvenNumber(arr[j])) {
//如果arr[j]是偶数，j向左移动
j --;
}
}
System.out.println("排序后的数组："+Arrays.toString(arr));
}
}
/**
* 是否是偶数
* @param num
* @return
*/
private boolean isEvenNumber(int num) {
return num % 2 == 0;
}
测试代码：
int[] arr2 = {8,9,3,1,5,6,10};
test03(arr2);
测试结果：
排序后的数组：[5, 9, 3, 1, 8, 6, 10]
可以看到输出结果中奇数在左边，偶数在右边，但打乱了顺序，下面对奇数和偶数分别进行从小到大排列
3.2实现代码（对奇数和偶数两组数据分别进行从小到大排列）：
public void test04(int[] arr) {
if (arr != null && arr.length > 0) {
List<Integer> oddList = new ArrayList<>();//奇数list
List<Integer> evenList = new ArrayList<>();//偶数list
int i = 0;
int j = arr.length - 1;
int temp;
while (i < j) {
if (isEvenNumber(arr[i]) && !isEvenNumber(arr[j])) {
//需要交换位置
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
if (!isEvenNumber(arr[i])) {
//如果arr[i]是奇数，i向右移动
i ++;
}
if (isEvenNumber(arr[j])) {
//如果arr[j]是偶数，j向左移动
j --;
}
}
for (int m=0;m<arr.length;m++) {
if (isEvenNumber(arr[m])) {
//偶数
evenList.add(arr[m]);
} else {
//奇数
oddList.add(arr[m]);
}
}
Collections.sort(oddList);
Collections.sort(evenList);
List<Integer> newList = new ArrayList<>();
newList.addAll(oddList);
newList.addAll(evenList);
Log.i(TAG, "排序后的数组："+newList.toString());
System.out.println("排序后的数组："+newList.toString());
}
}
/**
* 是否是偶数
* @param num
* @return
*/
private boolean isEvenNumber(int num) {
return num % 2 == 0;
}
4.在Java中如何从给定排序数组中删除重复项?
问题简述：
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
参考：https://blog.csdn.net/weixin_46703995/article/details/127849601
/**
* 在Java中如何从给定排序数组中删除重复项?
* @param arr
* @return 返回新数组的长度（忽略原有数组的长度）
*/
public int removeDuplicates(int[] arr) {
if (arr.length <= 1) {
return arr.length;
}
int slow = 0;
/**
* 原始数组：int[] arr3 = {1,3,3,5,6,6,8};
* 第一步：slow = 0, fast = 1 -> slow = 1; arr[slow]=3; -> 结果：arr3= {1,3,3,5,6,6,8};
* 第二步：slow = 1, fast = 2 -> slow = 1; arr[slow]=3; -> 结果：arr3= {1,3,3,5,6,6,8};没变化
* 第三步：slow = 1, fast = 3 -> slow = 2; arr[slow]=5; -> 结果：arr3= {1,3,5,5,6,6,8};
* 第四步：slow = 2, fast = 4 -> slow = 3; arr[slow]=6; -> 结果：arr3= {1,3,5,6,6,6,8};
* 第五步：slow = 3, fast = 5 -> slow = 3; arr[slow]=6; -> 结果：arr3= {1,3,5,6,6,6,8};没变化
* 第六步：slow = 3, fast = 6 -> slow = 4; arr[slow]=8; -> 结果：arr3= {1,3,5,6,8,6,8};
*/
for (int fast = 1;fast < arr.length;fast++) {
if (arr[slow] != arr[fast]) {
slow ++;
arr[slow] = arr[fast];
}
}
return slow + 1;
}
测试代码：
int[] arr = {1,3,3,5,6,6,8};
int newArrLength=removeDuplicates(arr);
Log.i(TAG, "arr="+Arrays.toString(arr)+", arrLength="+newArrLength);
结果：
arr=[1, 3, 5, 6, 8, 6, 8], newArrLength=5
其中新数组内容为数组的前5位，即[1,3,5,6,8]
