/*
求2有序N长数组,第K大的数
*/
#include <stdio.h>
#include <iostream>
#include <assert.h>
#include <algorithm>
#define min(x,y) (x)<(y) ? (x) : (y)
#define max(x,y) (x)>(y) ? (x) : (y)
const int N = 4;
using namespace std;
//方法一 注意 第K大,还有2个边际
int FindKth(int A[], int B[], int n, int low ,int high, int k)
{
int m=(low+high)/2+1;
if(low>high) return '\0';
if(k==m)
{
return A[m-1]<=B[0] ? A[m-1] : FindKth(A, B, n, low, m-2, k);
}
else if(k==(N+m))
{
return A[m-1]>=B[N-1] ? A[m-1] : FindKth(A, B, n, m, high, k);
}
else if(k<m+1) return FindKth(A, B, n, low, high-1, k);
else if(k>N+m) return FindKth(A, B, n, low+1, high, k);
else if (A[m-1]>B[k-m-1] && A[m-1]<B[k-m] )
{
return A[m-1];
}
else if(A[m-1]>B[k-m])
{
return FindKth(A,B,n,low ,m-2, k);
}
else return FindKth(A, B, n, m, high, k);
}
int Find_Kth_IN_Arrays(int A[], int B[], int n, int k)
{
int value=FindKth(A, B, n, 0, n-1, k);
if(value=='\0') value=FindKth(B, A, n, 0, n-1, k);
return value;
}
//方法二,
int FindKthElement(int a[], int b[], int k)
{
if(k == 1)
return min(a[0], b[0]);
else if(k == N * 2)
return max(a[N - 1], b[N - 1]);
int left = max(k - N - 1, 0), right = N - 1;
while(left <= right)
{
int mid = (left + right) / 2;
if(mid + 1 == k)
{
if(a[mid] < b[0])
return a[mid];
else
right = mid - 1;
}
else if(mid + 1 + N == k)
{
if(a[mid] > b[k - mid - 2])
return a[mid];
else
left = mid + 1;
}
else
{
if(a[mid] > b[k - mid - 2] && a[mid] < b[k - mid - 1])
return a[mid];
else if(a[mid] > b[k - mid - 2] && a[mid] > b[k - mid - 1])
right = mid - 1;
else
left = mid + 1;
}
}
return FindKthElement(b, a, k);
}
int main()
{
int K;
int a[] = {1, 3, 7, 8};
int b[] = {2, 4 , 5, 6};
while(cin >> K)
{
assert(K >= 1 && K <= N * 2);
cout << FindKthElement(a, b, K) << endl;
cout<<Find_Kth_IN_Arrays(a, b, 4, K)<<endl;
}
return 0;
}
分享到:
相关推荐
算法:给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = ...
本文实例讲述了Python实现的合并两个有序数组算法。分享给大家供大家参考,具体如下: 思路 按位循环比较两个数组,较小元素的放入新数组,下标加一(注意,较大元素对应的下标不加一),直到某一个下标超过数组长度...
# 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 # 请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) # 你可以假设 nums1 和 nums2 不同时为空 # 示例 1: # nums1 = [1, 3] # nums2 = [2] #...
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例1: nums1 = [1, 3] ...
两个升序的数组A、B,将AB合并到C,保持升序,去除重生的元素
主要介绍了合并有序数组的实现(java与C语言)的相关资料,这里对有序数组的合并分享了java版本和C语言版本的示例,需要的朋友可以参考下
具体来说,假设待合并的两个有序数组分别为A和B,它们的长度分别为n和m,合并后的有序数组为C,那么合并的过程可以按如下步骤进行: 1. 定义三个指针i、j和k,分别指向数组A、B和C的起始位置。 2. 比较A[i]和B[j]的...
数组a中已存有互不相同的10个整数从键盘输入一个整数,找出与该值相同的数组元素下标。 (如果没找到,输出“没找到”).c
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。 说明: 返回的下标值(index1 和 index2)不是从零开始的...
你可以假设数组递增有序。 请在O(N)时间内完成。 输入 第一行:N个整数,作为数组的元素,空格分开 第二行:target 输出 两个下标,空格隔开。如有多组满足要求,输出靠前的一组。 样例输入 4 2 7 11 15 9 样例输出 ...
在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。 完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只...
两个有序数组,假设是从大到小排序的,一次循环合并两个数组,合完也是从大到小的顺序。
题目描述:给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 num1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以...
无法登录两个有序数组的中位数 LeetCode 中“无重复字符的最长子串”问题的解决方法。 问题 有两个大小分别为 m 和 n 的排序数组 nums1 和 nums2。 找出两个已排序数组的中位数。 整体运行时间复杂度应该是 O(log (m...
一个简单的有序数组合并算法:写一个函数,传入 2 个有序的整数数组,返回一个有序的整数数组。实现相当简单,创建一个长度为这两个长度之和的数组,然后分别用三个指针指向这三个数组,找到这两个数组中各个元素在...
它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个有序的子序列组成,每个子序列的长度为1,然后再两两合并,得到了一个 N/2 个长度为2或1的有序子序列,再两两合并,如此重复,直到得到一个长度为N的...
(4) 给定一个有序数组(均小于 FFH 例如 02H, 07H, 0BH, 0FH, 13H, 1CH, 24H, 39H, 40H, 57H, 68H)和一个目标值(例如 79H),请判断数组中是否含有两个数的 和为目标值,请设计一个算法,将时间复杂度控制在 O(n...
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。 请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。 你可以假设 nums1 和 nums2 不同时为空。 示例 1: nums1 = [1, 3] nums2 = ...
leetcode 答案 leetcode LeetCode刷题记录 demo1: 题目:给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 注意: demo2: ...成为一个有序数组。
本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法。分享给大家供大家参考。具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入...