一. 找出数组中的重复数字
在一个长度为n的数组 nums 中，所有的数字都在0 ~ n-1的范围内。数组中的某些数字是重复的，但是不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字
【示例】
输入[2，3，1，0，2，5，3] 输出 2或3；
解法①：集合的解法
使用集合存储已遍历过的数据，新数据遍历时，只需要判断在集合中是否存在，如果存在即为重复数字
public static int findRepeatNumber(int[] nums){HashSet<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {int num = nums[i];if (set.contains(num)){return num;}set.add(num);}return -1;}
解法②：先排序后查找
排序后，重复元素是相邻的，这时候判断相邻元素是否重复即可。
public static int findRepeatNumber1(int[] nums){//先对数组进行排序Arrays.sort(nums);//遍历数组for (int i = 1; i < nums.length; i++) {int num = nums[i];//判断相邻数组是否相等if (num == nums[i-1]){return num;}}return -1;}
解法③：临时数组
因为长度为n的数组它所有的元素的大小都在0~n-1，所以临时数组中的索引对应原数组中所有可能出现的数字，遍历时，将元素数值对应的临时数组索引位置的元素的元素值进行更改，通过判断临时数组的该索引位置上的数值是否为0即可得出重复元素的值
public static int findRepeatNumber2(int[] nums){//声明一个长度相同的临时数组，以记录nums出现情况int[] tmp = new int[nums.length];for (int i = 0; i < nums.length; i++) {//判断遍历拿到的元素是否已出现过if (tmp[nums[i]] == 1){return nums[i];}//将该元素在临时数组中对应的下标位置元素值修改为1tmp[nums[i]] = 1;}return -1;}
解法④：位值匹配（交换位置查找重复元素）
遍历数组的过程中，希望当前位置和出现元素正好匹配上，先判断是否匹配，如果不匹配，进行交换。并且看需要交换的位置是否存在期望元素。如果可以交换，交换之后继续遍历当前位置。如果不可以交换，即为重复元素
【示例】
[1, 2, 3, 4, 5, 2]
[2, 1, 3, 4, 5, 2]
[3, 1, 2, 4, 5, 2]
[4, 1, 2, 3, 5, 2]
[5, 1, 2, 3, 4, 2]
[2, 1, 2, 3, 4, 5]
下标为:0位置处出现重复元素:2
public static int findRepeatNumber3(int[] nums){System.out.println(Arrays.toString(nums));for (int i = 0; i < nums.length; i++) {//先判断当前位置处索引与元素数值是否相等，如果相等直接contine跳过if (nums[i] == i){continue;}//如果不相等，判断i下标位置处数值与数值对应下标位置处数值是否相等，如相等说明为重复数字if (nums[i] == nums[nums[i]]){System.out.println("下标为:"+i +"位置处出现重复元素:"+nums[i]);return nums[i];}//经过上面两层判断如果都未通过，调换位置，将i下标位置处数值放入数值对应下标的相应位置int tmp = nums[nums[i]];nums[nums[i]] = nums[i];nums[i] = tmp;//调换完位置后，仍需要从当前位置重新遍历，也就是说调换过来的数值仍旧需要比对，i--抵消此次循环i--;System.out.println(Arrays.toString(nums));}return -1;}
二、找出所有的数组中消失的数字
【描述】给定一个范围在 1<= a[ i ] <= n(n为数组大小)的整型数组，数组中的元素一些出现了两次，一些出现了一次，找出所有[1,n]范围之内没有出现在数组中的数字。
解法①：使用容器存储已出现的数字
遍历该数组，将数组内元素都放置进一个set集合中，然后遍历该数组的下标，判断下标如果不在该set集合中，即为该数组内缺失的数字，返回即可；
public static List<Integer> findDisappearedNumber(int[] nums){HashSet<Integer> set = new HashSet<>();List<Integer> resultList = new ArrayList<>();for (int num : nums) {set.add(num);}for (int i = 1; i <= nums.length; i++) {if (!set.contains(i)){resultList.add(i);}}return resultList;}
解法②：利用数组本身索引比对数值
遍历该数组，拿到数组内元素，该元素的值对应数组内的下标，将该下标位置上的元素设为其相反数。经过一轮遍历，如果某个索引位置上的数值仍为正数，说明数组内没有元素与该索引位置对应，则该索引位置的索引数值+1即为数组内消失的数字。将其放置进list集合，返回即可。
【说明】其本质就是给数值对应的出现位置打标，如果某个位置未打标，证明该位置对应数值未出现
【过程演示】
[2, 6, 1, 3, 1, 3]
[2, -6, 1, 3, 1, 3]
[2, -6, 1, 3, 1, -3]
[-2, -6, 1, 3, 1, -3]
[-2, -6, -1, 3, 1, -3]
[-2, -6, -1, 3, 1, -3]
[-2, -6, -1, 3, 1, -3]
下标为3处的值为正，对应未出现数值为4
下标为4处的值为正，对应未出现数值为5
[4, 5]
public static List<Integer> findDisappearedNumber1(int[] nums) {List<Integer> resultList = new ArrayList<>();System.out.println(Arrays.toString(nums));for (int i = 0; i < nums.length; i++) {int num = Math.abs(nums[i]);int index = num -1;if (nums[index] > 0){nums[index] = -nums[index];}System.out.println(Arrays.toString(nums));}for (int i = 0; i < nums.length; i++) {int num = nums[i];if (num > 0){resultList.add(i+1);System.out.println("下标为"+i+"处的值为正，对应未出现数值为"+(i+1));}}return resultList;}
三、找出已知已存在多数元素的数组内的多数元素
【描述】给定一个大小为n的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 n/2的元素。可以假定前提：该数组内的元素都是非空的，并且该数组内是存在多数元素的
解法①：Map容器记录法
使用Map容器，键记录数组内元素，值记录该元素在数组内出现的次数。当某一个元素出现的次数大于数组长度length的一半时，此元素即为多数元素
public static int majorityElement(int[] nums){//map容器用于记录元素及其出现次数HashMap<Integer, Integer> map = new HashMap<>();int len = nums.length;int halfLen = len / 2;for (int i = 0; i < nums.length; i++) {int count = 1;//map中如果已出现过该元素，取出其次数count，并加1if (map.containsKey(nums[i])){count = map.get(nums[i]);count++;}map.put(nums[i],count);//如果次数大于数组长度的一半，直接return该元素if (count > halfLen){return nums[i];}}return -1;}
解法②：排序后取中间元素
将数组内元素按照大小排序，这时候数组中间位置的元素即为多数元素
public static int majorityElement1(int[] nums){
Arrays.sort(nums);
int halfLen = nums.length/ 2;
return nums[halfLen];
}
解法③：投票算法
【分析】如果一个数组内存在多数元素，那么该元素出现的次数一定比其他所有元素出现次数乃至它们的和都要多。所以候选人的次数经过抵消之后，最终剩余的一定是多数元素
public static int majorityElement2(int[] nums){
//候选人，初始化为 -1；出现次数初始化置为0;
int candidate = -1;
int count = 0;
for (int i = 0; i < nums.length; i++) {
//如果count为0，将当前遍历的元素置为候选人，这样即使第一次遍历也可以将首元素置为候选人
if (count == 0){
candidate = nums[i];
}
//如果候选人与当前遍历元素相等，将次数加一，不等将次数减一
if (candidate == nums[i]){
count++;
}else {
count--;
}
}
return candidate;
}
四、稀疏数组的转换
一个二维数组如果其元素数值大部分为0或者某一个固定数值，只有个别位置为特殊数值，可以通过转换成int[count+1][3]的形式，其中count为原二维数组内的元素个数。通过转换可以压缩数据占用空间大小。
【转换示例】：
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 3 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
—————————————————————
10 10 3
1 2 1
2 2 3
3 1 2
Process finished with exit code 0
① 二维数组转稀疏数组：
public static void main(String[] args) {
int[][] arr = new int[10][10];
arr[1][2] = 1;
arr[3][1] = 2;
arr[2][2] = 3;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + "\t");
}
System.out.println();
}
System.out.println("----------------------");
int[][] result = toSparse(arr);
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result[0].length; j++) {
System.out.print(result[i][j] + "\t");
}
System.out.println();
}
}
public static int[][] toSparse(int[][] arr){
int count = 0;
//先计算出二维数组一共有多少个有效数值
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if (arr[i][j] != 0){
count++;
}
}
}
//new 一个二维数组，一维长度为有效数值个数+1（因为要记录一组基本数据），二维长度为3
int[][] result = new int[count+1][3];
result[0][0] = arr.length;
result[0][1] = arr[0].length;
result[0][2] = count;
//遍历该二维数组，如果其中某一个数值有效，记录下其行数和列数，分别放入二维长度的0，1，2下标处
int index = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if (arr[i][j] != 0){
index++;
result[index][0] = i;
result[index][1] = j;
result[index][2] = arr[i][j];
}
}
}
return result;
}
② 稀疏数组转二维数组：
public static int[][] to2DArr(int[][] arr){
//依据稀疏数组记录的二维数组基础信息即第一行的三个信息，new出对应的二维数组
int[][] result = new int[arr[0][0]][arr[0][1]];
//依据下面的行数、列数及值等信息写入二维数组的对应位置
for (int i = 1; i < arr.length; i++) {
result[arr[i][0]][arr[i][1]] = arr[i][2];
}
return result;
}
【注】：可以这么理解，二维数组就是地图，有横纵坐标或者经纬度，而稀疏数组只记录经纬度。通过二维数组的地图可以找出其中某几个点对应的经纬度信息，也可以通过经纬度去判断出该位置在地图上的具体位置。
猜测：如果数值记录为地图上某一点的高度，那么这是不是就是三维地图的标的或者转换算法？
五、数组经典算法思想之双指针
类型①：删除排序数组中的重复项
给定一个元素已按大小排好顺序的数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，并返回移除后数组的长度。如给定数组为[0,1,1,1,2,3]，处理后的数组应为[0,1,2,3,2,3]并返回数组4；
public static int removeDuplicates(int[] nums){
if (nums.length == 0){return 0;};
//index记录当前要对比的元素数值
int index = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[index] != nums[i]){
//如果对比后数值不等，需要更新index数值，把不等的元素放入新index处，并继续对比
index++;
nums[index] = nums[i];
}
}
//最终数组内有效元素个数为index+1
return index+1;
}
类型②：移除元素
给定一个数组 nums和一个值val，你需要原地移除所有值等于val的元素，并返回移除后数组的新长度。不需要使用额外的数组空间，你必须仅使用O(1)额外空间并原地修改输入数组。元素的顺序可以改变，你不需要考虑新数组中超出新长度后面的元素。
解法①：依次遍历并比较
一个指针遍历数组内元素，并依次与val值进行比较，另一个指针记录要插入的元素位置。当元素值与val值不相等时，把该元素值插入第二个指针记录的位置处，并更新第二个指针，然后继续比较和插入过程。
public static int removeElement(int[] nums,int val){
if (nums.length == 0){return 0;}
//第二个指针，记录要插入或修改的元素位置
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val){
nums[index] = nums[i];
System.out.println("将数值:"+nums[i]+"覆盖到下标"+index+"位置处");
index++;
}
}
System.out.println(Arrays.toString(nums));
return index;
}
解法②：交换删除
解法①的方式是判断给定“数组内元素是否与给定val不等”，不等的话需要挪动元素到前面位置。如果数组内只有一个首位元素是相等的，那也需要移动后面数个元素，效率不高。交换删除的逻辑是判断“数组内元素是否与给定val相等”，相等的话与倒数元素进行替换，并逻辑上减小数组长度-1，然后再拿交换过来的元素继续对比。
public static int removeElement1(int[] nums,int val){
//首先声明数组长度，以获取倒数元素的值
int len = nums.length -1;
int index = 0;
while(true){
//判断挪动指针的index下标是否超过或等于len，如果为true，该值即为有效元素个数
if (index >= len){return len;}
//遍历数组内元素，判断元素值与给定val是否相等，相等的话与倒数元素进行替换
if (nums[index] == val){
nums[index] = nums[len];
nums[len] = val;
System.out.println("---" + Arrays.toString(nums));
len--;
//需要抵消掉index++，以继续对替换过来的元素进行对比判断
index--;
}
System.out.println(Arrays.toString(nums));
index++;
}
}
若有收获，就点个赞吧
0 人点赞
