目录
约瑟夫环问题
寻找第k小的数
2sum 3sum问题
数组中超过一半或者超过1/3的数
约瑟夫环问题
/**
* https://blog.csdn.net/weixin_38214171/article/details/80352921
*/
public class JosephCircle {
public static void main(String[] args) {
System.out.println(joseph(5,3));
System.out.println(LastRemaining_Solution(5,3));
}
public static int joseph(int count,int doom){
int alive = count; //幸存人数
int number = 0; //计数，number==dom时，淘汰这个人
int index = 0; //下标，为总人数-1
//0表示这个人在约瑟夫环内，1表示这个人在约瑟夫环外
int[] circle = new int[count];
//只要幸存人数>0,则一直进行
while (alive>0){
number += 1-circle[index];
if(number == doom){ //当number==dom时，就要淘汰这个人
/**
* 淘汰一个人分四步
* 1.输出这个人的位置
* 2.把这个人的状态从圈内0，改为状态1
* 3.幸存人数alive--；
* 4.计数number归零
*/
System.out.println(index+1);
circle[index] = 1;
alive--;
number = 0;
}
//与总人数count取余，则可以使index在0~count-1之间 一直循环，达到循环数组的目的
index = (index+1)%count;
System.out.println("index="+index);
}
if(index == 0){
return count;
}
return index;
}
/**
* 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。
* HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:
* 首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。
* 每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,
* 从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,
* 可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。
* 请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
* @param n 小朋友的个数
* @param m 报数
* @return
*/
public static int LastRemaining_Solution(int n, int m) {
int alive = n;
int[] help = new int[n];
int index = 0;
int cur = -1;
while (alive>0){
cur+= 1-help[index];
if(cur == m-1){
help[index] = 1;
alive--;
cur = -1;
}
index = (index+1)%n;
}
if(index == 0){
return n-1;
}
return index-1;
}
}
寻找第k小的数
1.用大根堆 此方法时间复杂度为O(N*logk)，因为二叉堆的插入和删除操作都是logk的时间复杂度。不详细说明
2.借助快排的思想
/**
* 时间复杂度为O(n)
* 复杂度：平均情况下，遍历一次数组找到哨兵是n，下一次就是n/2，最后到1，中间最多需要k次（k=lg2n）
* 等比数列求和：n+n/2+n/4+n/8+…+1 = 2n
*/
public class FindkthInArray {
public static void main(String[] args) {
int[] array = {92, 5, 88, 13, 80,7};
System.out.println(findKthLargest(array,5));
}
public static int findKthLargest(int[] nums,int k){
return findK(nums,k,0,nums.length-1);
}
private static int findK(int[] nums, int k, int start, int end) {
int low = start;
int high = end;
int key = nums[low];
while (low<high){
while (low<high&&nums[high]>=key){
high --;
}
nums[low] = nums[high];
while (low<high &&nums[low]<=key){
low++;
}
nums[high] = nums[low];
}
nums[low] = key;
if(low == k-1){
return key;
}else if(low>k-1){
return findK(nums, k, start, low-1);
}else {
return findK(nums, k, low+1, end);
}
}
}
2sum 3sum问题
2sum问题比较简单。不再赘述，直接借用set数组能解决
3sum问题有两种思路。
思路一：先排序。然后转化为先固定a。排序好的b+c=0的问题。b的坐标从a的坐标+1开始，c从最右边开始。b和c相中家夹逼。
时间复杂度 。排序O(NlgN),后面的过程为O(n^2).所以总的时间复杂度为O(n^2)
public class Sum3 {
public static void main(String[] args) {
int[] nums = {-1, 0, 1, 2, -1, -4};
System.out.println(threeSum(nums));
}
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length<3){
return result;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length-2;) {
int j = i+1;
int k = nums.length-1;
while (j<k){
if(nums[j]+nums[k]+nums[i] == 0){
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
result.add(list);
j++;
k--;
// 从左向右找第一个与之前处理的数不同的数的下标,去除重复元素
while (j<k&&nums[j]==nums[j-1]){
j++;
}
// 从右向左找第一个与之前处理的数不同的数的下标
while (j<k&&nums[k]==nums[k+1]){
k--;
}
}else {
if(nums[j]+nums[k]+nums[i] < 0){
j++;
// 从左向右找第一个与之前处理的数不同的数的下标
while (j<k&&nums[j]==nums[j-1]){
j++;
}
}else {
k--;
// 从右向左找第一个与之前处理的数不同的数的下标
while (j<k&&nums[k]==nums[k+1]){
k--;
}
}
}
}
// 指向下一个要处理的数
i++;
// 从左向右找第一个与之前处理的数不同的数的下标
while (i < nums.length - 2 && nums[i] == nums[i - 1]) {
i++;
}
}
return result;
}
}
数组中超过一半或者超过1/3的数
/**
* 超过一半
*
* @param nums
* @return
*/
public static int moreThanHalf(int[] nums) {
int a = nums[0];
int cnta = 0;
for (int num : nums) {
//如果是a的话，计数+1
if (num == a) {
cnta++;
continue;
}
//如果不是a，且计数不为0，将其赋值给a
if (cnta == 0) {
a = num;
cnta = 1;
continue;
}
//如果不是a，且a的计数不为0，那么就都删除，表现为a的数量减1
cnta--;
}
cnta = 0;
for (int num : nums) {
if (num == a) {
cnta++;
}
}
if (cnta <= nums.length / 2) {
return 0;
}
return a;
}
/**
* 超过1/3
*
* @param nums
* @return
*/
public static List<Integer> majorityElement(int[] nums) {
ArrayList<Integer> ans = new ArrayList<>();
if (nums == null || nums.length == 0) {
return ans;
}
int a = nums[0];
int cnta = 0;
int b = nums[0];
int cntb = 0;
for (int num : nums) {
//num = a或者num = b，计数+1
if (num == a) {
cnta++;
continue;
}
if (num == b) {
cntb++;
continue;
}
//如果既不是a，也不是b，a或者b的个数为0，那么将这个值付给a或者b
if (cnta == 0) {
a = num;
cnta = 1;
continue;
}
if (cntb == 0) {
b = num;
cntb = 1;
continue;
}
//有三个不一样的数就将他们都删除
cnta--;
cntb--;
}
for (int num : nums) {
if (num == a) {
cnta++;
} else {
if (num == b) {
cntb++;
}
}
}
if (cnta > nums.length / 3) {
ans.add(a);
}
if (cntb > nums.length / 3) {
ans.add(b);
}
return ans;
}
转载请注明原文地址: https://ju.6miu.com/read-350008.html
