剑指offer
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
方法一：逐位判断根据 与运算 定义，设二进制数字 n，则有：若 n & 1 = 0，则 n 二进制 最右一位 为 0 ；若 n & 1 = 1 ，则 n 二进制 最右一位 为 1 。根据以上特点，考虑以下 循环判断 ：判断 n最右一位是否为 1 ，根据结果计数。将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用 无符号右移 操作）。算法流程：初始化数量统计变量 res = 0循环逐位判断： 当 n = 0时跳出。res += n & 1 ： 若 n & 1 = 1 ，则统计数 res加一。n >>= 1 ： 将二进制数字 n无符号右移一位（ Java 中无符号右移为 ">>>" ） 。返回统计数量 res。
复杂度分析：时间复杂度 O(log_2 n)： 此算法循环内部仅有移位、与、加 等基本运算，占用 O(1) ；逐位判断需循环 log_2 n次，其中 log_2 n代表数字 n 最高位 1 的所在位数（例如 log_2 4 = 2, log_2 16 = 4）。空间复杂度 O(1) ： 变量 res 使用常数大小额外空间。
public class Solution { public int hammingWeight(int n) { int res = 0; while(n != 0) { res += n & 1; n >>>= 1; } return res; }}
方法二：巧用 n & (n - 1))(n - 1) 解析： 二进制数字 n 最右边的 1 变成 0 ，此 1右边的 0 都变成 1 。n & (n - 1) 解析： 二进制数字 n 最右边的 1 变成 0 ，其余不变。
算法流程：初始化数量统计变量 res 。循环消去最右边的 1 ：当 n=0 时跳出。res += 1 ： 统计变量加 1 ；n &= n - 1 ： 消去数字 n 最右边的 1 。返回统计数量 res。
复杂度分析：时间复杂度 O(M) ： n & (n - 1) 操作仅有减法和与运算，占用 O(1) ；设 M 为二进制数字 n 中 1 的个数，则需循环 M 次（每轮消去一个 1 ），占用 O(M) 。空间复杂度 O(1) ： 变量 res 使用常数大小额外空间。
public class Solution {
public int hammingWeight(int n) {
int res = 0;
while(n != 0) {
res++;
n &= n - 1;
}
return res;
}
}
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
解题思路：第一时间想到的解法：双指针先遍历统计链表长度，记为 n ；设置一个指针走 (n−k) 步，即可找到链表倒数第 k 个节点。使用双指针则可以不用统计链表长度。
作复杂度分析：时间复杂度 O(N) ： N 为链表长度；总体看， former 走了 N 步， latter 走了 (N−k) 步。空间复杂度 O(1)： 双指针 former , latter 使用常数大小的额外空间。
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode f = head;
ListNode l = head;
for(int i=0;i<k;++i){
f=f.next;
}
while(f!=null){
f=f.next;
l=l.next;
}
return l;
}
}
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
【解题思路1】排序出现次数最多的元素大于n/2次的就是众数，暴力法会超时，所以可以先排序，然后下标是n/2的元素一定是众数，n为奇数或者偶数都可以。
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
时间复杂度：O(nlogn)。将数组排序的时间复杂度为 O(nlogn)。空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。如果自己编写堆排序，则只需要使用 O(1) 的额外空间。
【解题思路2】map
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int n = nums.length / 2;
for(int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
if(map.get(num) > n) {
return num;
}
}
return 0;
}
}
时间复杂度：O(n)，其中 n 是数组 nums 的长度。遍历数组 nums 一次，对于 nums 中的每一个元素，将其插入哈希表都只需要常数时间。如果在遍历时没有维护最大值，在遍历结束后还需要对哈希表进行遍历，因为哈希表中占用的空间为 O(n)，因此总时间复杂度为 O(n)。空间复杂度：O(n)。哈希表最多包含 n - ⌊n/2⌋ 个键值对，所以占用的空间为 O(n)。这是因为任意一个长度为 n 的数组最多只能包含 n 个不同的值，但题中保证 nums 一定有一个众数，会占用（最少）⌊n/2⌋ + 1 个数字。因此最多有 n - (⌊n/2⌋ + 1) 个不同的其他数字，所以最多有n - ⌊n/2⌋ 个不同的元素。
【解题思路2】摩尔投票法：设输入数组 nums 的众数为 x，数组长度为 n 。推论一： 若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。推论二： 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n-a)个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的众数仍为 x 。
根据以上推论，假设数组首个元素 n_1为众数，遍历并统计票数。当发生票数和 =0 时，剩余数组的众数一定不变 ，这是由于：当 n_1 =x ： 抵消的所有数字，有一半是众数 xx 。当 n_1 !=x ： 抵消的所有数字，少于或等于一半是众数 x 。利用此特性，每轮假设发生 票数和 =0 都可以 缩小剩余数组区间 。当遍历完成时，最后一轮假设的数字即为众数。
算法流程:初始化： 票数统计 votes = 0 ， 众数 x；循环： 遍历数组 nums 中的每个数字 num ；当 票数 votes 等于 0 ，则假设当前数字 num 是众数；当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 ；返回值： 返回 x 即可；
复杂度分析：
时间复杂度 O(N) ：* NN* 为数组 nums 长度。
空间复杂度 O(1)：votes 变量使用常数大小的额外空间。
考虑 数组不存在众数 的情况。若考虑，需要加入一个 “验证环节” ，遍历数组 nums 统计 x 的数量。
若 x 的数量超过数组长度一半，则返回 x ；否则，返回未找到众数；
class Solution {
public int majorityElement(int[] nums) {
int vote=0;
int x = 0;
for(int n : nums){
if(vote ==0){
x=n;
}
vote += n==x ? 1: -1;
}
int count=0;
for(int n :nums){
if(n==x){
count++;
}
}
return count > (nums.length/2) ? x : 0;
}
}
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
方法一：排序
思路和算法
对原数组从小到大排序后取出前 k个数即可。
复杂度分析
时间复杂度：O(nlogn)，其中 n是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。
空间复杂度：O(logn)，排序所需额外的空间复杂度为 O(logn)。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
Arrays.sort(arr);
return Arrays.copyOf(arr,k);
}
}
方法二：堆思路和算法
我们用一个大根堆实时维护数组的前 k小值。首先将前 k个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。使用 PriorityQueue默认升序需要自定义比较器
复杂度分析
时间复杂度：O(nlogk)，其中 n 是数组 arr 的长度。由于大根堆实时维护前 k小值，所以插入删除都是 O(logk) 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 O(nlogk) 的时间复杂度。
空间复杂度：O(k)，因为大根堆里最多 k 个数。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(k==0){
return new int[0];
}else if(k>=arr.length){
return arr;
}
Queue<Integer> queue = new PriorityQueue<>((v1,v2)->v2-v1);
for(int i=0;i<k;++i){
queue.offer(arr[i]);
}
for(int i=k;i<arr.length;++i){
if(queue.peek()>arr[i]){
queue.poll();
queue.offer(arr[i]);
}
}
int[] result = new int[k];
for(int i=0;i<k;++i){
result[i]=queue.poll();
}
return result;
}
}
方法三：快排思想
思路和算法
借鉴快速排序的思想。我们知道快排的划分函数每次执行完后都能将数组分成两个部分，小于等于分界值 pivot 的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标。与快速排序不同的是，快速排序会根据分界值的下标递归处理划分的两侧，而这里我们只处理划分的一边。
复杂度分析
时间复杂度：期望为 O(n) ，由于证明过程很繁琐，所以不再这里展开讲。具体证明可以参考《算法导论》第 9 章第 2 小节。
最坏情况下的时间复杂度为 O(n^2)。情况最差时，每次的划分点都是最大值或最小值，一共需要划分 n - 1次，而一次划分需要线性的时间复杂度，所以最坏情况下时间复杂度为 O(n^2)
空间复杂度：期望为 O(logn)，递归调用的期望深度为 O(logn)，每层需要的空间为 O(1)，只有常数个变量。
最坏情况下的空间复杂度为 O(n)。最坏情况下需要划分 n 次，即 randomized_selected 函数递归调用最深 n−1 层，而每层由于需要 O(1) 的空间，所以一共需要 O(n) 的空间复杂度
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(k==0){
return new int[0];
}else if(k>=arr.length){
return arr;
}
partitionArray(arr,0,arr.length-1,k);
return Arrays.copyOf(arr,k);
}
void partitionArray(int[] arr, int l, int r, int k){
int n = partition(arr, l, r);
if(n==k){
return;
} else if(n<k){
partitionArray(arr,l+1,r,k);
} else{
partitionArray(arr,l,n-1,k);
}
}
int partition(int[] arr, int lo, int hi){
int i = lo;
int j= hi+1;
int ret = arr[lo];
while(true){
while(arr[++i]<ret){
if(i==hi){
break;
}
}
while(arr[--j]>ret){
if(j==lo){
break;
}
}
if(i>=j){
break;
}
swap(arr,i,j);
}
swap(arr,lo,j);
return i;
}
void swap(int[] arr, int i,int j){
int temp = arr[i];
arr[i] =arr[j];
arr[j] = temp;
}
}
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
解题思路：此题求拼接起来的 “最小数字” ，本质上是一个排序问题。排序判断规则： 设 nums 任意两数字的字符串格式 x 和 y ，则若拼接字符串 x + y > y + x ，则 m > n；反之，若 x + y < y + x ，则 n < m ；根据以上规则，套用任何排序方法对 nums 执行排序即可。
算法流程：初始化： 字符串列表 strs ，保存各数字的字符串格式；列表排序： 应用以上 “排序判断规则” ，对 strs执行排序；返回值： 拼接 strs中的所有字符串，并返回。复杂度分析：
时间复杂度O(NlogN) ： N 为最终返回值的字符数量（ strs 列表的长度 ≤N ）；使用快排或内置函数的平均时间复杂度为 O(NlogN) ，最差为 O(N^2)。空间复杂度 O(N) ： 字符串列表 strs 占用线性大小的额外空间。
快速排序
class Solution {
public String minNumber(int[] nums) {
int n = nums.length;
String[] num = new String[n];
for(int i=0;i<n;i++){
num[i] = String.valueOf(nums[i]);
}
quickSort(num,0,n-1);
StringBuilder sb = new StringBuilder();
for(String s : num){
sb.append(s);
}
return sb.toString();
}
void quickSort(String[] num, int l, int r){
if(l>=r){
return;
}
int i = l;
int j= r;
String init= num[l];
while(i<j){
while((num[j]+num[l]).compareTo(num[l]+num[j])>=0&&i<j){
j--;
}
while((num[i]+num[l]).compareTo(num[l]+num[i])<=0&&i<j){
i++;
}
String temp= num[i];
num[i]=num[j];
num[j]=temp;
}
num[l]=num[j];
num[j]=init;
quickSort(num,l,j-1);
quickSort(num,j+1,r);
}
}
内置函数
class Solution {
public String minNumber(int[] nums) {
return Arrays.stream(nums).boxed().map(i->i.toString())
.sorted((x,y)->(x+y).compareTo(y+x)).collect(Collectors.joining(""));
}
}
统计一个数字在排序数组中出现的次数。
一.解题思路：
判空，以及target是否在数组最小值与最大值之间，如果不是返回0二分查找大于target的第一个元素的下标，然后二分查找大于target-1的第一个元素的下标，然后二者相减即得最终结果二分查找首先定义左右指针，左指针初始0，右指针初始这项数组最后一个元素当左指针小于等于右指针时，找到左右指针的中间指针，当中指针小于等于target时，说明在中指针右边的值才可能大于target，则左指针等于中指针加1当中间指针大于target时，则比target大的指针可能在中间指针之前或者就是中间指针，此时将中间指针减1赋值给r当比target大的指针是中指针时，则中间指针减1后一定小于等于target，此时将中间指针减1赋值给右指针，之后一直循环下去，每次都是左指针等于新的中指针加1,直到左指针等于右指针加1结束循环，因为之前右指针时中间指针-1，此处再加1，所以左指针就等于中间指针当比target大的指针在中指针左边时，会按照步骤4继续循环二.时间复杂度：o(logN)三.空间复杂度：o(1))
如上图所示，由于数组 nums中元素都为整数，因此可以分别二分查找 target 和 target - 1的右边界，将两结果相减并返回即可。
本质上看， helper() 函数旨在查找数字 tartar 在数组 nums 中的 插入点 ，且若数组中存在值相同的元素，则插入到这些元素的右边。
class Solution {
public int search(int[] nums, int target) {
return helper(nums, target) - helper(nums, target - 1);
}
int helper(int[] nums, int tar) {
int i = 0, j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] <= tar) i = m + 1;
else j = m - 1;
}
return i;
}
}
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
解题思路：排序数组中的搜索问题，首先想到 二分法 解决。根据题意，数组可以按照以下规则划分为两部分。左子数组： nums[i] = i ；右子数组： nums[i] !=i ；缺失的数字等于 “右子数组的首位元素” 对应的索引；因此考虑使用二分法查找 “右子数组的首位元素” 。
算法解析：初始化： 左边界 i = 0 ，右边界 j = len(nums) - 1 ；代表闭区间 i, j 。循环二分： 当 i≤j 时循环 （即当闭区间 i, j 为空时跳出） ；计算中点 m = (i + j) / 2；若 nums[m] = m，则 “右子数组的首位元素” 一定在闭区间 m + 1, j 中，因此执行 i = m + 1；若 nums[m] ！=m ，则 “左子数组的末位元素” 一定在闭区间 i, m - 1 中，因此执行 j = m - 1；返回值： 跳出时，变量 i 和 j 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 i即可。
复杂度分析：
时间复杂度 O(log N)： 二分法为对数级别复杂度。
空间复杂度 O(1)： 几个变量使用常数大小的额外空间。
class Solution {
public int missingNumber(int[] nums) {
int i = 0, j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] == m) i = m + 1;
else j = m - 1;
}
return i;
}
}
