整理不易留个小心心呗🥰
如果有更好的或者是我有错的地方还请各位大佬指出哦
有些是copy的还望不要介意

排序与检索

• • • 最大数
    • 摆动排序Ⅱ
    • 寻找峰值
    • 寻找重复数

最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例：

输入：nums = [10,2]
输出："210"

• 代码实现

class Solution {public String largestNumber(int[] nums) {int n = nums.length;String[] words = new String[n];for(int i=0;iwords[i] = String.valueOf(nums[i]);}Arrays.sort(words,(a,b)->{//(b+a)>(a+b)则返回1,则交换ab位置成为bareturn (b+a).compareTo(a+b);});//第一个为0后面的一定小于等于它if(words[0].equals("0")){return "0";}StringBuilder sb = new StringBuilder();for(int i=0;isb.append(words[i]);}return sb.toString();}
}

摆动排序Ⅱ

题目描述：
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。

示例：

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

• 代码实现

  为了防止相邻的数相同，排序后最大的数从后往前取，当然小的数也要这样

class Solution {public void wiggleSort(int[] nums) {int[] cp = Arrays.copyOf(nums, nums.length);Arrays.sort(cp);//排好序后小的数从前半部分取，大的数从后半部分取for(int idx = 0, i = (nums.length -1)/2, j = nums.length - 1; idx < nums.length; i--, j--, idx++) {nums[idx++] = cp[i];if(idx < nums.length) {nums[idx] = cp[j];}}}
}

进阶:你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

提示：

1 <= nums.length <= 5 * 104
0 <= nums[i] <= 5000
题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

• 桶排序

class Solution {public void wiggleSort(int[] nums) {//5001个桶int[] bucket = new int[5001];for(int num:nums){bucket[num]++;}int j=5000;//插空放入大的数for(int i=1;i//该值桶内元素用完则到下一个桶while(bucket[j]==0){j--;}nums[i] = j;bucket[j]--;}//插空放入小的数for(int i=0;iwhile(bucket[j]==0){j--;}nums[i] = j;bucket[j]--;}}
}

寻找峰值

题目描述：
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题

示例：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

提示：
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

• 寻找最大值

class Solution {public int findPeakElement(int[] nums) {int index = 0;for(int i=1;iif(nums[index]index = i;}}//不满足前一个比现到的大则返回return index;}
}

• 二分查找

class Solution {public int findPeakElement(int[] nums) {int left = 0,right = nums.length-1;while(leftint mid = left + (right - left)/2;//往大的一边(往上爬)查找一定有峰值if(nums[mid] > nums[mid + 1]){right = mid;}else{left = mid + 1;}}return left;}
}

寻找重复数

题目描述：
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间

示例：

输入：nums = [1,3,4,2,2]
输出：2

提示：
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：
如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

• 模拟链表

将索引和值建立一个映射关系，以索引为0出发，再根据他的值为新索引，以此遍历
0→1
1→3
3→2
2→4
4→2
出现重复数则会构成一个环，以此找出环的入口便可

class Solution {public int findDuplicate(int[] nums) {int slow = 0,fast = 0;slow = nums[slow];fast = nums[nums[fast]];while(slow!=fast){slow = nums[slow];fast = nums[nums[fast]];}int pre1 = 0;int pre2 = slow;while(pre1!=pre2){pre1 = nums[pre1];pre2 = nums[pre2];}return pre1;}
}