char a[]={"str1", "str2"} 这个其实就是二维数组了,但声明只有一维,所以从第2个开始就报错了。
char jibenjqiguanxi[8][7] = {"爸爸","妈妈","兄弟","姐妹","丈夫","妻子","儿子","女儿"}; // 长度7,UT8一个汉字一般3字节,一个\0,编码不同、内容不同这个值也不同
printf("%s", jibenjqiguanxi[0]); // 输出"爸爸"
char daishuweier[8][8][7] = {
{"爷爷","奶奶"},
{"外公","外婆"}
};
printf("%s", daishuweier[0][0]); // 输出"爷爷"
根据题意,我们只需要取出最小的前K
个数即可,那我们便可以不对数组进行排序,而是利用小堆
的特性:每个父亲结点的值总是≤
孩子结点的值
只需要对这个数组进行建堆
(建成小堆)即可,然后每次都取出根节点
(最小值),一共取K
次,便是最小的前K
个元素
❗特别注意:
堆
,再进行使用👉实现:
1️⃣实现堆
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void Swap(HPDataType* p1, HPDataType* p2);
void AdjustDwon(HPDataType* a, int size, int parent);
void AdjustUp(HPDataType* a, int child);
void HeapDestroy(HP* php);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void HeapInit(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
//1.拷贝
memcpy(php->a, a, sizeof(HPDataType)*n);
php->size = n;
php->capacity = n;
//2.建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDwon(php->a, php->size, i);
}
}
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0)
while (child > 0)
{
//if (a[child] < a[parent])
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//建小堆
void AdjustDwon(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
// 选出左右孩子中小/大的那个
if (child+1 < size && a[child+1] < a[child])
{
++child;
}
// 孩子跟父亲比较
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&(php->a[0]), &(php->a[php->size - 1]));
php->size--;
AdjustDwon(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
2️⃣实现Top-K
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
HP hp;
HeapInit(&hp,arr,arrSize);
int* retArr = (int*)malloc(sizeof(int)*k);
for(int i = 0;i < k; i++)
{
retArr[i] = HeapTop(&hp);
HeapPop(&hp);
}
HeapDestroy(&hp);
*returnSize = k;
return retArr;
}
💫但目前
堆
的效率为:O(N+k∗logN)O(N + k*logN)O(N+k∗logN),是否还能优化呢?⭐答案是可以的