2001. 可互换矩形的组数-快速排序

2001. 可互换矩形的组数-快速排序

用一个下标从 0 开始的二维整数数组 rectangles 来表示 n 个矩形，其中 rectangles[i] = [widthi, heighti] 表示第 i 个矩形的宽度和高度。

如果两个矩形 i 和 j（i < j）的宽高比相同，则认为这两个矩形 可互换 。更规范的说法是，两个矩形满足 widthi/heighti == widthj/heightj（使用实数除法而非整数除法），则认为这两个矩形 可互换 。

计算并返回 rectangles 中有多少对 可互换 矩形。

示例 1：

输入：rectangles = [[4,8],[3,6],[10,20],[15,30]]
输出：6
解释：下面按下标（从 0 开始）列出可互换矩形的配对情况：

• 矩形 0 和矩形 1 ：4/8 == 3/6
• 矩形 0 和矩形 2 ：4/8 == 10/20
• 矩形 0 和矩形 3 ：4/8 == 15/30
• 矩形 1 和矩形 2 ：3/6 == 10/20
• 矩形 1 和矩形 3 ：3/6 == 15/30
• 矩形 2 和矩形 3 ：10/20 == 15/30

示例 2：

输入：rectangles = [[4,5],[7,8]]
输出：0
解释：不存在成对的可互换矩形。

这题我们需要先转化一下数组形势，一维转化为二维，解题代码如下：

int cmp(double *a, double *b)
{       
    return *a>*b;
}
 void  f(double *a,int low,int high){
     if(low<high){
     int l=low;
     int h=high;
    
     int index=low+rand()%(high-low);
     double t=a[index];
     a[index]=a[low];
     a[low]=t;
      double p=a[low];
     
      if(low<high){
       while(low<high){
        // printf("fsa");
         while(a[high]>=p&&low<high){
             
             high--;
         }
         a[low]=a[high];
         while(a[low]<=p&&low<high){
             low++;
         }
         a[high]=a[low];

     }
     a[low]=p;
     f(a,l,low-1);
     f(a,low+1,h);
    }
    }
 }
long long interchangeableRectangles(int** rectangles, int rectanglesSize, int* rectanglesColSize){
    double *ratio=(float *)malloc(sizeof(double)*rectanglesSize);
    for(int i=0;i<rectanglesSize;i++){
        ratio[i]=rectangles[i][0]*1.0/(1.0*rectangles[i][1]);
    }
    qsort(ratio,rectanglesSize,sizeof(double),cmp);
     double target=ratio[0];
    int pre_index=0;
    long long re=0;
    int i;
  
    for(i=1;i<rectanglesSize;i++){
        if(target!=ratio[i]){
          
            int num=i-pre_index;
            pre_index=i;
            target=ratio[i];
           
         
            re=re+num*(num-1)/2;
        }
      
        
    }
    int num=i-pre_index;
    
    re=re+(long long )num*(num-1)/2;


    return re;

}













1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83