只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
异或，相同为0，不同为1，所以任何数和0做异或都是等于本身，本身和本身异或为0
class Solution {
public int singleNumber(int[] nums) {
int r = 0;
for(int i=0;i<nums.length;i++){
r = r^nums[i];
}
return r;
}
}
只出现一次的数字Ⅱ
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,99]
输出：99
数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3的倍数。
因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。
class Solution {
public int singleNumber(int[] nums) {
int r = 0;
for(int i=0;i<32;i++){//对每一位
int count = 0;//统计数组中所有数字的二进制 在 i 位上 是 1 的个数
for(int j=0;j<nums.length;j++){
if(((nums[j]>>i)&1)==1){//nums[j] 二进制 i 位 上是否是 1
count++;
}
}
if(count%3==0){
continue;
}else{
//i 位上 1 的个数不是 3 的倍数，因为只出现了 1 次的数贡献出了 1
r = r | (1<<i);
}
}
return r;
}
}
寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
class Solution {
public int findDuplicate(int[] nums) {
int slow=0,fast=0;
while(true){
slow = nums[slow];
fast = nums[nums[fast]];
if(slow==fast){//相遇了，但是不是在入环口 根据定律：入环口到相遇点的距离（，即慢指针还需要走的路程到入环点->包含转圈圈的）等于起点到入环口的的距离
fast = 0;
while(nums[fast]!=nums[slow]){
slow=nums[slow];
fast=nums[fast];
}
return nums[slow];
}
}
}
}
存在重复元素 2
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
滑动窗口 + 哈希表
整理题意：是否存在长度不超过的 k+1 窗口，窗口内有相同元素。
我们可以从前往后遍历 nums，同时使用 Set 记录遍历当前滑窗内出现过的元素。
假设当前遍历的元素为 nums[i]：下标小于等于 k（起始滑窗长度还不足 k+1）：直接往滑窗加数，即将当前元素加入 Set 中；下标大于 k：将上一滑窗的左端点元素 nums[i−k−1] 移除，判断当前滑窗的右端点元素 nums[i] 是否存在 Set 中，若存在，返回 True，否则将当前元素 nums[i] 加入 Set 中。重复上述过程，若整个 nums 处理完后仍未找到，返回 False。
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
int n = nums.length;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
if (i > k) set.remove(nums[i - k - 1]);
if (set.contains(nums[i])) return true;
set.add(nums[i]);
}
return false;
}
}
数组中最小正整数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for(int i=0;i<n;i++){
if(nums[i]<=0){
nums[i]=n+1;
}
}
for(int i=0;i<n;i++){
//得到该数的绝对值
int t = Math.abs(nums[i]);
if(t>n){
continue;
}
nums[t-1]=-1*Math.abs(nums[t-1]);
}
for(int i=0;i<n;i++){
if(nums[i]>0){//表示没有数来覆盖这个位置
return i+1;
}
}
return n+1;
}
}
丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
找缺失数、找出现一次数都是异或的经典应用。
我们可以先求得 [1,n] 的异或和 ans，然后用 ans 对各个 nums[i] 进行异或。这样最终得到的异或和表达式中，只有缺失元素出现次数为 1 次，其余元素均出现两次（x⊕x=0），即最终答案 ans 为缺失元素。
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int r = 0;
for(int i=0;i<=n;i++){
r = r^i;
}
for(int i=0;i<n;i++){
r = r^nums[i];
}
return r;
}
}
错误的集合
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1：
输入：nums = [1,2,2,4]
输出：[2,3]
示例 2：
输入：nums = [1,1]
输出：[1,2]
class Solution {
public int[] findErrorNums(int[] nums) {
int n = nums.length;
int xor = 0;
for(int i=1;i<=n;i++){
xor = xor ^ i;
}
for(int i=0;i<n;i++){
xor = xor ^ nums[i];
}
int lowBit = xor & (xor ^ (xor-1));
int num1 = 0;
int num2 = 0;
for(int i=1;i<=n;i++){
if((i & lowBit) ==0){
num1 = num1 ^ i;
}else{
num2 = num2 ^ i;
}
}
for(int i=0;i<n;i++){
if((nums[i] & lowBit) ==0){
num1 = num1 ^ nums[i];
}else{
num2 = num2 ^ nums[i];
}
}
for(int i=0;i<n;i++){
if(nums[i]==num1){
return new int[]{num1,num2};
}
}
return new int[]{num2,num1};
}
}
小于n的最大值-字节面试题
数组A中给定可以使用的1~9的数，返回由A数组中的元素组成的小于n（n > 0）的最大数。 例如：A = {1, 2, 4, 9}，n = 2533，返回2499。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
private static int result = 0;
public static void main(String[] args) {
int[] nums = new int[]{1,2,4,9};
int target = 2533;
List<Integer> sk = new ArrayList<>();
Arrays.sort(nums);
getMinNMax(nums,sk,target);
System.out.println(result);
}
public static void getMinNMax(int[] nums,List<Integer> sk,int target){
int r = getSum(sk);
if(r<target){
result = Math.max(r,result);
}
if(r>=target){
return;
}
for(int i=0;i< nums.length;i++){
sk.add(nums[i]);
getMinNMax(nums,sk,target);
sk.remove(sk.size()-1);
}
}
public static int getSum(List<Integer> sk){
int r = 0;
int t = 1;
for(int i=sk.size()-1;i>=0;i--){
r+=t*sk.get(i);
t*=10;
}
return r;
}
}
