package offer;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
//找出数组中重复的数字。
//在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。
// 数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
public class Test1 {
public static void findNums() {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();//输入数组的个数
//构建数组
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
//判断每个数组出现的次数
//新建一个计数器数组 count 取值范围1-n次
int count[] = new int[n];
for (int i = 0; i < n; i++) {
count[i] = 1;
for (int j = i + 1; j < n; j++) {
if (nums[i] == nums[j])
count[i]++;
}
}
for (int i = 0; i < n; i++) {
if (count[i] >= 2)
System.out.println(nums[i]);
}
}
//方法二 set只能放一个数一次 当不能放的时候就错了哈希
public int findNumsSet() {
//新建一个set
Set set = new HashSet<>();
int[] nums = new int[10];//数组
//记录标识
int flag = -1;
for (int num : nums) {
//每次添加 要是添加不进去就错误
if (!set.add(num)) {
flag = num;
}
//退出 保存了flag的值
break;
}
return flag;
}
//时间复杂度为n的计算方法
//先把每个数放在自己应该在的位置上 取值范围0-n-1
public int findNumsN() {
int[] nums = new int[10];//数组
int n = nums.length;
//n为数组的长度
//先排除不符合题意的情况
//0123 四个数只能范围到3 如果有一个数为4就不符合题意
for (int num : nums)
if (num < 0 || num >= n)
return -1;
//交换数组内容值
for (int i = 0; i < n; i++) {
//应该在这个位置上面的数 不是这个
while (nums[i] != i && nums[nums[i]] != nums[i]) {
//交换两个的位置
int tmp = nums[i];
nums[i] = nums[nums[i]];
nums[nums[i]] = tmp;
}
//交换完成以后
if (nums[i] == i && nums[nums[i]] == nums[i])
return nums[i];
}
return -1;
}
public static void main(String[] args) {
//首先输入数组
findNums();
}
}
- 找重复的数值
package offer;
import java.util.Scanner;
//在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
// 请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
public class Test2 {
public static int[][] input() {
int[][] matrix = new int[5][5];
Scanner sc = new Scanner(System.in);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
matrix[i][j] = sc.nextInt();
}
}
return matrix;
}
public static boolean findTarget(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == target)
return true;
}
}
return false;
}
//方法二 按照行列剔除某一行某一列 选左下角跟右上角
public static boolean findTarget2(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0 || matrix == null)
return false;
//m行值 n列值 从左下角看
int m = matrix.length, n = matrix[0].length;
int i = 0, j = n - 1;
while (i < m && j >= 0) {
int num = matrix[i][j];
if (num == target) {
return true;
} else if (num > target) {
j--;
} else i++;
}
return false;
}
public static void main(String[] args) {
int[][] matrix = input();
Scanner sc = new Scanner(System.in);
int target = sc.nextInt();
System.out.println(findTarget(matrix, target));
}
}