1. 剑指Offer 03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
思路：
- 利用桶排序的思想，在空间要求不严格的时候可以使用
- 输入的每个数相当于桶的下标；循环遍历数组，将每个数字对应的桶数组中的值++；
- 如果大于等于2，就返回桶下标
题解:
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int size =nums.size();
//temp为桶
int temp[size];
memset(temp,0,sizeof temp);
int i;
for(i=0;i<=size;i++)
{
temp[nums[i]]++;
if(temp[nums[i]]>=2)
{
return nums[i];
}
}
return 0;
}
};
java:利用HashSet集合的性质，add的元素已存在时，返回false。
class Solution {
public int findRepeatNumber(int[] nums) {
HashSet<Integer> hashSet = new HashSet<Integer>();
for (int i : nums) {
if (!hashSet.add(i))
{
return i;
}
}
return 0;
}
}
复杂性分析
时间复杂度：O(n)O(n)O(n)。
遍历数组一遍。使用哈希集合（HashSet），添加元素的时间复杂度为 O(1)O(1)O(1)，故总的时间复杂度是 O(n)O(n)O(n)。
空间复杂度：O(n)O(n)O(n)。不重复的每个元素都可能存入集合，因此占用 O(n)O(n)O(n) 额外空间。
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/mian-shi-ti-03-shu-zu-zhong-zhong-fu-de-shu-zi-b-4/
来源：力扣（LeetCode）
2. 剑指 Offer 04. 二维数组中的查找
难度简单
描述：
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
方法1：暴力搜索，直接二重循环查找
方法2：官方题解给出的方法，从右上角开始查询：row和column分别为二维数组的行和列，初始row为0，column为matrix[0].length-1；当前元素值大于target时，column--；小于时，row++；
跳出循环条件：row<matrix.length，column>=0；
代码：
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
boolean res = false;
//这里要判断一下x和y是否等于0
int x = matrix.length;
int y = matrix[0].length;
int row = 0, column = y-1;
int temp;
while(row <= x-1 && column>=0)
{
temp = matrix[row][column];
if(temp == target)
{
res = true;
break;
}
if(temp > target)
{
column -= 1;
}
else
{
row += 1;
}
}
return res;
}
}
方法3：每一行做一次二分查找。截至条件跟上个方法类似，matrix[i][matrix[0].length-1](每行最右的元素)如果大于target就说明可能存在target；如果小于就可以不用查找当前行；如果matrix[i][0]大于target就说明不可能查到了。
（这个方法居然比官方给的题解快 ）
代码：
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
boolean res = false;
int x = matrix.length;
if(x == 0)
return false;
int y = matrix[0].length;
if(y == 0)
return false;
for (int[] ints : matrix) {
int high = y-1;
int low = 0;
if (ints[y - 1] < target)
continue;
else if (ints[0] > target)
break;
else {
while (low <= high) {
if (ints[low] == target || ints[high] == target) {
res = true;
break;
}
if(high - low == 1)
break;
if (ints[(low + high) / 2] < target) {
low = (low + high) / 2 ;
} else
high = (low + high) / 2 ;
}
}
3. 美团笔试Q1：
- 要求：买蛋糕，n为每天可以做出的蛋糕数目；m为已经做出的蛋糕数目；每个蛋糕有个整数重量。顾客要买蛋糕中最轻和最重的两个，且重量为a，b；蛋糕可以现做。
- 输入输出：两行数据，第一行为四个数据：n, m, a, b。第二行为已经做好的蛋糕数量。问是否能满足顾客需求，能输出"YES"，否则输出"NO"。
- 例如输入：
4 2 1 3
2 2
输出：YES - 代码：
import java.util.Arrays;
import java.util.Scanner;
public class Q1 {
public static void main(String[] args) {
int cake[] = new int[1000];
Scanner s = new Scanner(System.in);
int n,m,a,b;
while(true)
{
n=s.nextInt();
m = s.nextInt();
a = s.nextInt();
b = s.nextInt();
for(int i = 0; i<m; i++)
{
cake[i] = s.nextInt();
}
Arrays.sort(cake,0, m);
if(a==b)
{
System.out.println("NO");
}
else if(a>b)
{
comp(cake, n, m, b, a);
}
else if(a<b)
{
comp(cake, n, m, a, b);
}
else
System.out.println("NO");
}
}
private static void comp(int[] cake, int n, int m, int a, int b) {
if(b == cake[m-1])
{
if(a ==cake[0])
System.out.println("YES");
else if(n-m >= 1 && a <=cake[0])
System.out.println("YES");
else
System.out.println("NO");
}
else if(a ==cake[0])
{
if(b == cake[m-1])
System.out.println("YES");
else if(n-m >= 1 && b >= cake[m-1])
System.out.println("YES");
else
System.out.println("NO");
}
else if(b>=cake[m-1] && a<=cake[0] && n-m >=2)
{
System.out.println("YES");
}
else
System.out.println("NO");
}
}
4. 美团笔试Q2：计算晋级人数
- 要求：给出n个人的分数，以排名第m个人的分数为界限，不低于此分数且得分不为0的晋级。要求输出晋级人数。
- 输入输出：两行数据，第一行：人数n和m，第m个人的分数为晋级标准；第二行：n个人的分数
例如输入：
5 3
4 2 0 0 0
输出：
2 - 代码：
import java.util.Arrays;
import java.util.Scanner;
public class Q2{
public static void main(String[] args) {
int n,x;
int sum = 0,max;
Scanner s = new Scanner(System.in);
n = s.nextInt();
x = s.nextInt();
int p[] = new int[n];
for(int i = 0;i<n;i++)
{
p[i] = s.nextInt();
}
Arrays.sort(p);
max = p[n-x];
for(int i = n-1; i>=0; i--)
{
if(p[i]>=max && p[i]!=0)
{
sum++;
}
}
System.out.println(sum);
}
}
