时间复杂度
看看有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)，依此类推，如果有二分则为O(logn)，、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。
二分查找
二分查找的基本思想是：在有序表中，取中间元素作为比较对象，若给定值与中间元素相等，则查找成功；若给定值小于中间元素，则在中间元素的左半区继续查找；若给定值大于中间元素，则在中间元素的右半区继续查找。不断重复上述过程，直到找到为止。
从二分查找的定义我们可以看出，使用二分查找有两个前提条件：
（1）待查找的列表必须有序。
（2）必须使用线性表的顺序存储结构来存储数据。
int[] arr = new int[]{1, 3, 5, 6, 7, 8, 9};
int target = 8;//目标元素
int begin = 0;//开始位置
int end = arr.length - 1;//结束位置
int mid = (begin + end) / 2;//中间位置
int index = -1;//目标位置
//循环查找
while (true) {
if (arr[mid] == target) {
index = mid;
break;
} else {
//判断中间元素是不是比目标元素大
if (arr[mid] > target) {
end = mid - 1;//把结束为止调整到中间的前一个位置
} else {
begin = mid + 1;//把开始为止调整到中间的位置加1
}
mid = (begin + end) / 2; //取出新的中间位置
}
}
Log.w("TAG", "index---" + index);
冒泡排序
采用两两比较并交换位置的思路，就仿佛泡泡一样，较大的元素会慢慢“上浮”1从数列一端开始，比较相邻两个元素，如果第一个元素比第二个元素大，交换两个元素位置然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，2移动至下一对相邻元素，再次进行比较和交换，直到数列最后一个元素3保证倒数第一的元素是数列中最大的）4不断重复以上操作。每次重复的时候，需要比较的元素个数都减1
//冒泡排序
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {//大数在前则交换位置
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
选择排序
特点：每一轮都能选出最小的数 最外层开始选择第一个数和所有的开始比较，原理：每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。
public void choose() {
int[] arr = {5, 2, 8, 4, 9, 1};
//选择排序的优化
for (int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
for (int j = i + 1; j < arr.length; j++) {// 选最小的记录
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
Log.w("wangwei", "---" + Arrays.toString(arr));
}
快速排序
原理：选择一个关键值作为基准值，一般选择序列的第一个元素。分区，比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的再对左右区间重复第二步，直到各区间只有一个数
挖坑填数
将基准数挖出形成第一个坑由后向前找出比他小的数填入到第一次的坑中，由前向后找出比基准值打的数放入上一步拿出去的地方-重复执行2，3步。
会做n次二分 一次为logn n次则就是O（nlogn）
log 二分查找默认的底数为2
对数 x=log(a)(N) a的x次方等于N
//快速排序
public void getKuaiSu() {
int[] a = {5, 3, 9, 1, 6, 7, 2, 4, 0, 8};
quickSort(a, 0, a.length - 1); }
public void quickSort(int[] arr, int start, int end) {
if (start < end) {
int index = getIndex(arr, start, end);//分区索引位
quickSort(arr, 0, index - 1);
quickSort(arr, index + 1, end);
}
}
//分区并返回索引值
private int getIndex(int[] arr, int start, int end) {
//记录需要排序的下标
int i = start;
int j = end;
//第一个坑位，基准值，
int x = arr[i];
//循环找出比基准值大的数和比基准值小的数
while (i < j) {
//先从右向左对比找出小于x的数,arr[j] >= x，不需要移动数据，则继续往前走
while (i < j && arr[j] >= x) {
j--;
}
//比基准值小的时候会跳出上面的循环，交换数字
if (i < j) {
//把找到的元素放入第一个坑位
arr[i] = arr[j];
i++;
}
//先从左向右对比找出大于x的数
while (i < j && arr[i] < x) {
i++;
}
if (i < j) {
//把找到的元素放入第一个坑位
arr[j] = arr[i];
j--;
}
}
arr[i] = x;
return i;
}
插入排序
假设数列第一个元素为已排序数列，剩余数列为未排序将待排序元素挨个插入到已排序数列中每次插入都必须保证数列是有序的，即通过比较和移动有序数列中的元素，将元素插入到合适的位置
思路：如同玩扑克牌一样，每次摸牌都将它与手中的牌比较，始终将牌放在比它大的牌前面，比它小的牌后面。这样当牌全部摸到手上后，就是一个有序的序列。从后往前找合适的位置。
//遍历所有的数字，假定第一位已经排序，所以从arr[1]开始，
for (int i = 1; i < arr.length; i++) {
//如果当前数字比前一个小
if (arr[i] < arr[i - 1]) {
int temp = arr[i];
int j;
//遍历当前数字,前面的数字
for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
//把前一个数字给后面的
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}}
两个有序数组 找第k小
/**
* 两个有序数组 找第k小
* 方案一 合并遍历
* 二：游标计数
* 题目只要求第k大的数，没必要花力气将数组全部再排序，
* 可以定义两个游标分别指向两个有序数组，按序移动，并用count计数
* ，当count等于k时，返回两个游标指向的数中最小的那一个
*/
private int arrk() {
int K = 2;
int[] array1 = {3, 6, 7};
int[] array2 = {2, 8, 9};
int i = 0;
int j = 0;
int count = 0;
while (count < K - 1) {
if (array1[i] <= array2[j]) {
i++;
} else {
j++;
}
count++;
}
int ha = array1[i] >= array2[j] ? array2[j] : array1[i];
Log.w("TAG", "---ha-->" + ha);
return ha;
}
快速找出一个数组中的最大数、第二大数。
思路：如果当前元素大于最大数 max，则让第二大数等于原来的最大数 max， 再把当前元素的值赋给
* max。如果当前的元素大于等于第二大数secondMax的值 而小于最大数max的值，则要把当前元素的值赋给 secondMax。
*/ int[] arr = { 12, 49, 23, 32, 148, 48, };
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int secondMax = arr[0];
for (int j = 0; j < arr.length; j++) {
if (arr[j] > secondMax && arr[j] < max) {
secondMax = arr[j];
}
}
System.out.println("最大值:" + max + ",第二大数" +secondMax);
归并 合并两个数组
定义一个新数组，长度为两个数组长度之和，将两个数组都copy到新数组，然后排序。
给两个数组分别定义一个下标，最大长度是数组长度减一，按位循环比较两个数组，较小元素的放入新数组，下标加一（注意，较大元素对应的下标不加一），直到某一个下标超过数组长度时退出循环，此时较短数组已经全部放入新数组，较长数组还有部分剩余，最后将剩下的部分元素放入新数组，大功告成。
private void merge() {
int[] arr = {1, 4, 6, 7, 2};
int[] brr = {5, 8, 9, 15,1 7};
int[] x = new int[arr.length + brr.length];
//表示移动的指针
int ai = 0;
int bi = 0;
int xi = 0;
while (ai < arr.length && bi < brr.length) {
if (arr[ai] <= brr[bi]) {
x[xi++] = arr[ai++];
} else {
x[xi++] = brr[bi++];
}
}
while (ai < arr.length) {
x[xi++] = arr[ai++];
}
while (bi < brr.length) {
x[xi++] = brr[bi++];
}
Log.w("TAG", "--x--" + Arrays.toString(x));
}
归并排序
归并排序递归+合并 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
public static int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
sort(nums, low, mid); // 左边
sort(nums, mid + 1, high); // 右边
// 左右归并
merge(nums, low, mid, high);
}
return nums;
}
/**
* 待排序数组将数组中low到high位置的数进行排序@param low 待排的开始位置@param mid 待排中间位置@param high 待排结束位置
*/
public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
Log.w("wangwei", "---->--temp--" + Arrays.toString(temp));}
海量数据排序
采用外部排序
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
基本思路：外部排序指的是大文件的排序，即待排序的记录存储在外部存储器上，在排序过程中需进行多次的内、外存之间的交换。首先将打文件记录分成若干个子文件，然后读入内存中，并利用内部排序的方法进行排序；然后把排序好的有序子文件（称为：归并段）重新写入外存，再对这些归并段进行逐个归并，直到整个有序文件为止。
例子：假设有10 000个记录的文件需要排序，则先把这10 000个记录文件分成10个归并段（R1…~R10，每段1000个记录），然后逐个读入归并段进行内部排序（共10次），然后把排序好的归并段重新写入外存中，再进行两两归并，直到得到一个有序文件为止。
堆排序
堆是一个完全二叉树，不断的构造大顶堆，升序排列用大顶堆，降序排列用小顶堆
将数列中的元素构建成最大堆，作为无序区，记为H将无序区的根元素Hn和最后一个元素H1交换位置，则Hn成为有序区，H1至H(n-1)成为新无序区调整无序区，使其仍为最大堆重复第二、第三步操作，直到所有元素都进入有序区
TopK—返回第K小（大）的数字
1先用前k个元素生成一个小顶堆，这个小顶堆用于存储，当前最大的k个元素。
2接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替3换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。
直到，扫描完所有n-k个元素，最终堆中的k个元素，就是求的TopK。
找到单链表倒数第n个节点
第一种方法：单链表只有头指针，所以只能从头部开始寻找，先遍历一遍链表，确定链表中节点的个数k。然后从前往后第k-n+1个节点就是倒数第n个节点。一共遍历2次链表
第二种方法：先求出元素个数，在遍历元素个数-n个，时间复杂度为：O(N+N-n)=O(2N-n)。
private static Node findTailKth(Node head, int k) {
if (head == null || k <= 0) {
return null;
}
// 定义两个指针，fast先走k-1步，为什么要走k-1步，因为fast本身也是一步，在最后一个节点停下了，
// 所以slow距离最后一个节点的距离就是k - 1 + 1 = k
Node slow = head, fast = head;
for (int i = 0; i < k - 1; i++) {
if (fast.next != null) {
fast = fast.next;
} else {
return null;
}
}
// 然后两个指针一起走，直到fast走到链表的最后一个节点
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
有一个整形数组，包含正数和负数，然后要求把数组内的所有负数移至正数的左边，且保证相对位置不变，要求时间复杂度为O(n), 空间复杂度为O(1)。例如，{10, -2, 5, 8, -4, 2, -3, 7, 12, -88, -23, 35}变化后是{-2, -4，-3, -88, -23,5, 8 ,10, 2, 7, 12, 35}。
思路：两个变量，一个用来记录当前的遍历点，一个用来记录最左边的负数在数组中的索引值。然后遍历整个数组，遇到负数将其与负数后面的数进行交换，遍历结束，即可实现负数在左，正数在右。
二叉树
public class TreeNode { //二叉树的每一个节点
int value;//节点的值
//左儿子
TreeNode leftNode;
//右儿子
TreeNode rightNode;
public TreeNode(int value) {
this.value = value;
}
//设置左儿子
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
//设置右儿子
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
//先序遍历
public void frontShow() {
//先遍历当前节点的内容
Log.w("TAG", "----" + value);
//左节点
if (leftNode != null) {
leftNode.frontShow();
}
//右节点
if (rightNode != null) {
rightNode.frontShow();
}
}
//中序遍历
public void middleShow() {
//左节点
if (leftNode != null) {
leftNode.middleShow();
}
//先遍历当前节点的内容
Log.w("TAG", "----" + value);
//右节点
if (rightNode != null) {
rightNode.middleShow();
}
}
//层序遍历
/**
* 据层次遍历的顺序，每一层都是从左到右的遍历输出，借助于一个队列。
* 先将根节点入队，当前节点是队头节点，将其出队并访问
* ，如果当前节点的左节点不为空则将左节点入队，如果当前节点的右节点不为空将其入队。
* 所以出队顺序也是从左到右依次出队。
*/
public void levelIterator() {
LinkedList<TreeNode> queue = new LinkedList<>();
TreeNode current = null;
queue.offer(this);//将根节点入队
while (!queue.isEmpty()) {
current = queue.poll();//出队队头元素并访问
Log.w("TAG", "----" + current.value);
//如果当前节点的左节点不为空,入队
if (current.leftNode != null) {
queue.offer(current.leftNode);
}
//如果当前节点的右节点不为空，把右节点入队
if (current.rightNode != null) {
queue.offer(current.rightNode);
}
}
}
//-------------二叉树查找----------------
public TreeNode frontSearch(int i) {
TreeNode target = null;
if (this.value == i) {//对比当前节点的值
return this;
} else {
//当前节点不是要查找的节点，开始查找左节点
if (leftNode != null) {
//可能查不到，还是null
target = leftNode.frontSearch(i);
}
if (target != null) {
return target;
}
if (rightNode != null) { //查找右节点
target = rightNode.frontSearch(i);
}
if (target != null) {
return target;
}
}
return null;
}
//节点删除
public void delete(int i) {
TreeNode parent = this;
if (parent.leftNode != null && parent.leftNode.value == i) {
parent.leftNode = null;
return;
}
//判断右儿子
if (parent.rightNode != null && parent.rightNode.value == i) {
parent.rightNode = null;
return;
}
//递归检查并且删除左儿子
parent = leftNode;
if (parent != null) {
parent.delete(i);
}
parent = rightNode;
if (parent != null) {
parent.delete(i);
}
}
//二叉树 根 root
public class BinaryTree {
TreeNode root;
public void setRoot(TreeNode root) {
this.root = root;
}
//获取根节点
public TreeNode getRoot() {
return root;
}
//先序遍历
public void frontShow() {
root.frontShow();
}
//中序
public void middleShow() {
root.middleShow();
}
//层序
public void levelIterator() {
root.levelIterator();
}
//二叉树查找
public void frontSearch(int i) {
root.frontSearch(i);
}}
//创建二叉树
private void tree() {
//创建树
BinaryTree binaryTree = new BinaryTree();
//创建根节点
TreeNode root = new TreeNode(1);
// 把根节点赋给树
binaryTree.setRoot(root);
//创建一个左节点
TreeNode rootL = new TreeNode(2);
root.setLeftNode(rootL);
//创建一个右节点
TreeNode rootR = new TreeNode(3);
//把新的节点设置为根节点的右子节点
root.setRightNode(rootR);
//为第二层左节点创建两个子节点
rootL.setLeftNode(new TreeNode(4));
rootL.setRightNode(new TreeNode(5));
//为第二层右节点创建两个子节点
rootR.setLeftNode(new TreeNode(6));
rootR.setRightNode(new TreeNode(7));
//前序遍历 binaryTree.frontShow();
//中序遍历 binaryTree.middleShow();
//层序遍历 binaryTree.levelIterator();
//二叉树查找 binaryTree.frontSearch(3);}
二叉树节点查找，使用遍历的方式，查找到则有，
合并两个排序的链表
Step1.定义一个指向新链表的指针，暂且让它指向NULL；
Step2.比较两个链表的头结点，让较小的头结点作为新链表的头结点；
Step3.递归比较两个链表的其余节点，让较小的节点作为上一个新节点的后一个节点；
public Node Merge(Node head1, Node head2) {
if (head1 == null) {
return head2;
} else if (head2 == null) {
return head1;
}
Node newHead = null;
if (head1.Data <= head2.Data) {
newHead = head1;
newHead.Next = Merge(head1.Next, head2);
} else {
newHead = head2;
newHead.Next = Merge(head1, head2.Next);
}
return newHead;
}
输入两个链表，找出它们的第一个公共结点。
找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走
image.png
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
int len1 = findListLenth(pHead1);
int len2 = findListLenth(pHead2);
if(len1 > len2){
pHead1 = walkStep(pHead1,len1 - len2);
}else{
pHead2 = walkStep(pHead2,len2 - len1);
}
while(pHead1 != NULL){
if(pHead1 == pHead2) return pHead1;
pHead1 = pHead1->next;
pHead2 = pHead2->next;
}
return NULL;
}
int findListLenth(ListNode *pHead1){
if(pHead1 == NULL) return 0;
int sum = 1;
while(pHead1 = pHead1->next) sum++;
return sum;
}
ListNode* walkStep(ListNode *pHead1, int step){
while(step--){
pHead1 = pHead1->next;
}
return pHead1;
}
};
统计一个数字在排序数组中出现的次数。
思路：
1、顺序遍历
顺序扫描一遍数组，统计该数字出现的次数。
时间复杂度：O(n)
2、二分查找
假设我们需要找的数字是k，那么就需要找到数组中的第一个k和最后一个k出现的位置。
如何通过二分查找得到第一个k的位置呢？
取数组中间的数字与k作比较，
如果该数字比k大，那么k只能出现在前半部分，那么下一轮只能在前半部分找；
如果该数字比k小，那么k只能出现在后半部分，那么下一轮只能在后半部分找；
如果该数字等于k，需要判断这是不是第一个k，如果该数字的前一个数字不是k，那么该数字就是第一个k，否则需要在前半部分继续寻找第一个k；
寻找最后一个k的方法与寻找第一个k的方法一样。
找出数组中重复的数字
https://blog.csdn.net/m0_37925202/article/details/81415825
用两个栈实现一个队列的功能?要求给出算法和思路!
<分析>：
入队：将元素进栈A
出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；
如果不为空，栈B直接出栈。
用两个队列实现一个栈的功能?要求给出算法和思路!
<分析>：
入栈：将元素进队列A
出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素 以此出队列并放入队列B，直到队列A中的元素留下一个，然后队列A出队列，再把 队列B中的元素出队列以此放入队列A中。
网友评论